To: rusin@washington.math.niu.edu Subject: Re: Q: description of a surface Date: Tue, 10 Jan 95 15:20:43 +0100 From: mauricek@cs.kun.nl Dear Dave, Thank you for your answer to my question on sci.math. Although it was most comprehensible, I do have a few remarks and questions. > In article , > Maurice S klein Gebbinck wrote: > >In a 2-dim vector space lines through the origin can be evenly sampled using > >the direction vector (cos(a),sin(a)), with degrees of freedom (DF) = 1. In a > >3-dim space this can be done using (cos(a)cos(b),sin(a)cos(b),sin(b)), so DF=2. > >In general, for a R-dim space DF=R-1. > > Your use of this parameterization ("sampling") suggests that we don't agree > on what "evenly sampled" means. As b approaches pi/2 (90 degrees), your > many choices of a will give you lines very close together, and in fact at > b=pi/2 all choices of a give the same line. You're completely right! However, I don't know of a method that "samples more evenly" than the above. > > >Now lets consider surfaces through the origin. In a 3-dim space a possible way > > Caution: the word "surface" usually implies something wavy. What you mean > is "planes" (2-dimensional linear subspaces) through the origin. > > >of sampling is using the independent direction vectors (cos(a),0,sin(a)) and > >(0,cos(b),sin(b)), so DF=2. > > > >1. Is there a formula for EVENLY sampling surfaces in a 3-dim space? > > You can parameterize the planes as evenly as you did the lines, since the two > sets are in one-to-one correspondence: simply associate the line L with > the plane perpendicular to L. Of course, this has the same deficiency as > your previous solution: you will select certain planes more frequently if > you choose a and b randomly. True. What I'm really looking for is a parametrization for n>=3, with n according to your terminology below. > Your proposed solution makes me wonder if you really want planes or what > would be called "framed planes", that is, planes _with_ a basis given. You The method I use today indeed needs planes with a basis given. However, I think I could do with another description of the plane, for instance the normal vector in case n=3 and k=2. > need to decide whether two pairs of vectors which span the same plane > give you "surfaces" which you wish to consider as distinct or not. I have > answered above assuming that they would _not_ be considered different. > To see the distinction in the one-dimensional case, ask whether the > lines you have described as (cos(a), sin(a)) and (cos(a+pi), sin(a+pi)) > should be considered distinct or not. The choice is yours, but how you > phrase the question will affect the answer! Your assumption was correct, I do consider them to be the same > > >2. Can this formula be generalized for a R-dim space? > There are two dimensions relevant, and I don't know which you are calling > R. In general, you can ask about k-dimensional linear subspaces inside > an n-dimensional space. This is called the Grassmanian manifold. > The argument above, using orthoganality, shows that the sets of k-planes > and (n-k)-planes within n-space are in one-to-one correspondence. > (The collection of framed subspaces is the Stiefel manifold). Can you provide me with a pointer to these manifolds? > > >3. Am I correct that in a R-dim space the degrees of freedom equal 2(R-2)? > To find a k-plane in n-space, pick any non-zero vector as your first > basis vector (n degrees of freedom). Your second vector can be anything > linearly independent of the first (n-1 additional degrees of freedom). > Continue until you have k independent vectors (n + n-1 + ... + n-k+1 DF). > Then you probably want to call some of these sets "equal". Indeed, given > any one of those k-planes, you have k degrees of freedom for the first > vector, then k-1 for the next, and so on. Hence each k-plane shows up > a number of times, corresponding to k + k-1 + ... degrees of freedom. > Thus the set of really distinct k-planes only allows (n+...)-(k+...) > degrees of freedom. Using the formula 1+2+...+m=m(m+1)/2 you can deduce > that the number of degrees of freedom in the selection of k-planes in > n-space is (n-k)k. This is exactly what I am looking for. Now all I need is a procedure with (n-k)k parameters, preferable with a limited domain ([-\Pi/2,\Pi/2] for instance), which gives me the k independent vectors. Could the Stiefel manifold help me with this? > > [No jabs from purists here on accuracy of this derivation. I think I'm > responding at the poster's level.] Is it not accurate then? It looked accurate to me and yes, it is indeed my level. [sig deleted - djr] ============================================================================== Date: Wed, 11 Jan 95 12:49:34 CST From: rusin (Dave Rusin) To: mauricek@cs.kun.nl, rusin@washington.math.niu.edu Subject: Re: Q: description of a surface You wrote: >> >In 3-dim space this can be done using (cos(a)cos(b),sin(a)cos(b),sin(b)) >> Your use of this parameterization ("sampling") suggests that we don't agree >> on what "evenly sampled" means. As b approaches pi/2 (90 degrees), your >You're completely right! However, I don't know of a method that "samples more >evenly" than the above. Try this. Once you've picked b, the set of points you'll get by choosing different a's will trace out a circle of radius cos(b). Rather than allowing all a's in [0, 2pi], which would give you too many lines on the small circles, take values of x in [0, 2pi.cos(b)] and use the parameterization (cos(x/cos(b))cos(b), sin(x/cos(b))cos(b), sin(b)). The net effect is that (using the substitution a= x/cos(b)) you'll still trace out the same lines as before, but the different values of a that will be used will be fewer when cos(b) is smaller. Geometrically we would say that the mapping above carries the open region {(a, b) in R^2 : 0> >1. Is there a formula for EVENLY sampling surfaces in a 3-dim space? >> You can parameterize the planes as evenly as you did the lines >True. What I'm really looking for is a parametrization for n>=3, with n >according to your terminology below. I guess you must mean you need to parameterize the set of _planes_ (k=2) in n-space; the parameterization of _lines_ in n-space is classically the same as you have done for n=3: you just parameterize the top half of the sphere in n-space. This can be done with formulas like the ones you used for lines in 3-space: take the parameterization of the sphere in (n-1)-space, multiply each coordinate by cos(x_n) (where x_n is a new variable), then add a coordinate which is just sin(x_n). Let the old coordinates vary through the set you used to parameterize the whole sphere in (n-1)-space. You can either let x_n vary through [-pi/2 to pi/2] to get the whole sphere or through [0,pi/2] if you just want the upper hemisphere. You can even do this uniformly using ideas like I did for n=3. Simply arrange it so that x_n's with cos(x_n) close to zero are chosen less often. As indicated above, the problem is that the Jacobian determinant of the mapping in the previous paragraph isn't 1; you can show that it's a product of terms like cos(x_n)^(n-1). To fix this and get a volume- preserving map, we can compose with another map whose jacobian has determinant inverse to this. Somewhat unlike what I did in the case n=3, you can try setting x_n=f_n(y_n), where (by Chain Rule) the function f_n has to have derivative satisfying cos(f(y))^(n-1).f'(y) = 1, i.e. you have to satisfy the differential equation cos(f)^(n-1)df = dy. This is separable, with solution f = the inverse of g, where g is the antiderivative of cos(x)^(n-1). So in your parameterization choose your variables like this: For all spheres starting with the circle use: a: choose uniformly in [0, 2pi] For the sphere in 3-space and above add: b: let b=arcsin(y), y varying uniformly in [0,1] For the sphere in 4-space add: c: chose z uniformly in [0,pi/4] and solve for c in z=(1/2)[(sin 2c)/2 + c] The last formula is the most typical: in the general case you choose y_n uniformly and then solve for x_n from the equation y_n=\int cos(x_n)^(n-1) d(x_n). Presumably in a program you would solve for x_n using Newton's method or something. Note that in particular we get a handy area-preserving parameterization of the sphere in 3-space: let a and y vary uniformly and draw (sqrt(1-y^2) cos(a), sqrt(1-y^2) sin(a), y). >> >2. Can this formula be generalized for a R-dim space? >> There are two dimensions relevant, and I don't know which you are calling >> R. In general, you can ask about k-dimensional linear subspaces inside >> an n-dimensional space. This is called the Grassmanian manifold. >> The argument above, using orthoganality, shows that the sets of k-planes >> and (n-k)-planes within n-space are in one-to-one correspondence. >> (The collection of framed subspaces is the Stiefel manifold). >Can you provide me with a pointer to these manifolds? Well, there's a lot to say about them, but probably not much like what you're dealing with. You could take a look at Milnor's "Characteristic Classes" or any book dealing with "vector bundles" and you'll find them in there, but the attention pretty quickly turns to topological constructs like homology, so this can be pretty intimidating. >> >3. Am I correct that in a R-dim space the degrees of freedom equal 2(R-2)? >> To find a k-plane in n-space, pick any non-zero vector as your first >> basis vector (n degrees of freedom). Your second vector can be anything >> linearly independent of the first (n-1 additional degrees of freedom). >> Continue until you have k independent vectors (n + n-1 + ... + n-k+1 DF). >> Then you probably want to call some of these sets "equal". Indeed, given >> any one of those k-planes, you have k degrees of freedom for the first >> vector, then k-1 for the next, and so on. Hence each k-plane shows up >> a number of times, corresponding to k + k-1 + ... degrees of freedom. >> Thus the set of really distinct k-planes only allows (n+...)-(k+...) >> degrees of freedom. Using the formula 1+2+...+m=m(m+1)/2 you can deduce >> that the number of degrees of freedom in the selection of k-planes in >> n-space is (n-k)k. > >This is exactly what I am looking for. Now all I need is a procedure with >(n-k)k parameters, preferable with a limited domain ([-\Pi/2,\Pi/2] for >instance), which gives me the k independent vectors. Could the Stiefel >manifold help me with this? Would it be sufficient for your purposes to use the parameterization of the sphere, as given above, to select k points randomly on the sphere and use these for your basis? The Stiefel manifold is really just the collection of all such choices of k -tuples of vectors in n-space, excluding those k-tuples which are linearly dependent. Mathematically speaking this is really easy to treat, and theoretically this would be fine for applications since a randomly-selected k-tuple would be linearly dependent with probability zero. (For example, if you pick two points on the sphere, they will be linearly dependent in 3-space only if they are equal or opposite, which is not impossible but extremely unlikely!) I'm a little concerned about the possibility of round-off error and so on when doing this computationally. For example, if you select two points on the sphere which are very close together, then a small pertubation of one of them will greatly change the plane which passes through them. But hey, a plane's a plane. >> [No jabs from purists here on accuracy of this derivation. I think I'm >> responding at the poster's level.] >Is it not accurate then? It looked accurate to me and yes, it is indeed my >level. The problem here is that I am glossing over some fundamental geometric obstructions. The goal of "parameterizing" a set is usually to find some formula which sets up a one-to-one correspondence between the set and, say, an open subset of (flat) n-space. Implicit in this is the requirement that the map and, usually, its inverse map be continuous. In your case you seem to want the map also to be measure-preserving (area-preserving, etc.) Unfortunately, the existence of such a map would imply that the original set is geometrically the same as the open subset of R^n to which you are comparing it. Even if you drop the insistence on "even sampling" (measure-preservation), you would have to know that the set is topologically the same as the open subset in R^n. Well, for example, no matter how much you're willing to shrink or twist, you can't change the fact that the sphere in R^3 has a hole in it but no open subset in R^2 can have this kind of hole, so there can be no simple formula. (The usual parameterization of the sphere isn't really right: you can make it be one-to-one and onto and continuous if you make sure a and b are taken from just the right intervals, but then there is no inverse map which is continuous.) In fact this is already clear in the previous dimension: the circle can be parameterized by the map (cos(a), sin(a)), which is continuous, but for this map to be one-to-one and onto you need to take a to range over the interval [0, 2pi), say. Thus, if you look at the inverse map, pointing to different spots on the circle and asking what value of a will parameterize that spot, you'll see that points just under the right-most spot on the circle have values of a close to 2pi, but suddenly when you get to the right-most point you have to take a=0. Thus a correct statement about parameterizations would keep making references to "an open neighborhood around" various points. It is nice in this case that every point has a neighborhood that looks just like R^n, that is, the Grassmanian is indeed a manifold. You can imagine thing get more complex when you look, for example, at the set of points {(x,y): y^x=x^2-x^4} in the plane, which resembles a figure-8, and so has a point (0,0) whose neighborhoods do not look like open intervals. Furthermore, you'd need to say what it means to "use up" degrees of freedom; this is more correctly done using the construction of quotient spaces in topology. But that kind of objection is more a question of using language properly to make sure there is nothing odd happening; unlike the fundamental geometric obstructions I listed above, there is really no problem here, I've just glossed over the _verifications_ that there are no problems. -------------------- I've hesitated a little in my answers since I'm not sure how you will use this information. One person recently asked about a method to space about 10 000 points uniformly on a sphere (for some NASA experiment requiring a dimpled ball); another person wanted to select points on the sphere randomly (for a video game, I think). I see the problems as a little bit different since one asks for a fixed, single solution and the other asks for recurring, random patterns. I think the second is a little easier since I can exclude low-density difficult situations, whereas in the former the effects of the boundary on the parameterization are a little trickier. If you need further assistance on this problem, perhaps you can indicate how you need to use this information. good luck, dave. ============================================================================== Date: Fri, 27 Dec 1996 09:16:13 -0500 From: Ron Hardin To: rusin@math.niu.edu Subject: grassmanian packings [deletia -- djr] there's a paper in experimental mathematics 5:2 1996 on packings in grassmanian spaces, if it hasn't hit the press, and a collection of them in Neil Sloane's home page is under reconstruction at the moment -- Ron Hardin rhh@research.att.com On the internet, nobody knows you're a jerk. ============================================================================== From: "Ron Hardin" To: rusin@math.niu.edu Date: Thu, 9 Jan 1997 06:52:09 +0500 Subject: [none] grassmanian packings - the text at the end mentions putting 10k points on a sphere, incidentally; sloane has a directory of icosahedral packings that i think go up to 8k, and coverings and maxvols up to almost 100k, which are more suitable for dimpled balls i mention them because they're fairly pretty