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
**