Notional Slurry Logo

Just a smidge ana from there. No, a little kata now. Perfect!

November 30, 2005 at 10:55 pm · Filed under Uncategorized

Summary: I am going to ask a question about what seems to be simple differential geometry. It may be just about linear algebra. Me, I was a biologist for too long to remember any of this, alas. But I suppose since I’m a student these days, I should point out that it’s not for homework — it’s for an amusing project in genetic programming. But I really don’t have the mathematics to answer it with any certainty. So… anybody? help?

Say we have two points in two dimensions. Call them A and B. Together, A and B suffice to uniquely define a line, as long as they’re not coincident. As an ordered pair, (A,B) can be used to define a half-space in the plane: we can just, for instance, take the half of the plane that lies counter-clockwise from the vector connecting A to B. Positive axes, and all that. The line passing through AB is a hyperplane of dimension 1 lying in 2-space.

OK. Same drill in three-space. Three points A, B and C uniquely define a plane (which is itself 2-dimensional), as long as they’re not co-linear. We can take the ordered triple (A,B,C) and apply the right-hand rule to pick one side of the plane, and define a half-space.

You know where we’re going. Four dimensions. Four points uniquely define a 3D hyperplane, as long as they’re not coplanar (I suppose). That’s OK. Generally, in n dimensions, n points will uniquely define an n–1 dimensional hyperplane, as long as they’re linearly independent. But. But.

Does the ordered tuple (A,B,C,D) suffice to denote a unique half-space? I can see how it might, and at the same time I can see how it might not. Because there’s no clear definition of the cross product in 4D, so… what’s the equivalent of the right-hand rule? The top-hand rule, which will point in the anawards direction when you have your forefinger pointing in the first direction, your middle finger in the second direction, and your ring finger pointing in the third direction?

Ow. Oh, cool! My top thumb… like, disappeared. And here it is back again. Hunh.

Anyway.

Really, all I want to be able to do is come up with an unambiguous method for defining a specific half-space in n dimensions using n linearly independent points, (x1,x2,x3…xn). And I want the ordered tuple to be the only cue we use. Does it suffice?

If so, is it just the direction orthogonal to the all rays (x1,x2), (x2,x3), (x3,x4) … and (xn-1,xn)?

Wolfgang said,

December 1, 2005 @ 12:00 am

I guess you are looking for the wedge product
A /\ B /\ C /\ …. where A, B, C, … are the base vectors.
In index notation:
V_i = epsilon_{iabc..} A^a B^b C^c …

Wolfgang said,

December 1, 2005 @ 12:02 am

Oooops, I forgot:
with epsilon I mean of course the total antisymmetric symbol, (epsilon = +1, -1)

Wolfgang said,

December 1, 2005 @ 12:05 am

One more, the formula assumes summation over same indices and in Euclidean space you do not need to distinguish covariant and contravariant indices as I did.

By the way, I assume you were talking about flat Euclidean space, since in general your problem has no solution. E.g. on the torus a (closed) line does not always divide the manifold in two halfs.

B. Lane said,

December 1, 2005 @ 4:35 am

To elaborate:

The wedge product v1 ^ v2 ^ v3 ^ … ^ vn defines the n-form (roughly, n-plane) “containing” the vectors v1…vn. In three dimensions, for instance, the wedge product v ^ w of two vectors v and w defines the 2-plane containing them both. The normal vector to that plane is the cross product v x w. In 4-space, v ^ w defines a 2-plane again, but there is no “normal vector” to a plane in 4-space; this is why there’s no cross product.

Now, if you have _four_ points in 4-space, you have three vectors u, v, w, and u ^ v ^ w is a 3-plane, which has a normal vector. Five points in 5-space gives four vectors which wedge into a 4-plane, with a normal vector. We can use these normal vectors to tell which side of the plane a given point is on, just as in 2 and 3 dimensions, and thus we partition the space into two halves. This only works, though, as you point out, if the points are not coplanar - if you try to wedge a vector with a subplane it’s already in, the product is zero.

And, as Wolfgang points out, you can’t partition a general manifold in this way; it works in Euclidean n-space, though.

Tozier said,

December 1, 2005 @ 7:31 am

That seems like it’s the ticket!

The scoop is this: I’m framing an evolutionary search through the set of linear programming algorithms, and for generality’s sake am thinking of starting from a toolkit of simple (flat Euclidean) geometric operations, coupled with a representation of hyperplanes and half-spaces (linear inequality constraints) as n-point tuples.

So now, using the wedge product, we can describe a set of m inequality constraints on n variables as a list of m n-tuples of n-dimensional points. (Yes, there are very many such tuples which can define a given half-space. That’s one of the fun parts about this representation.) And the objective function as an n-dimensional vector.

The rest of the preparation is setting up some simple geometric functions for our evolving solvers to invoke: shortest distances, norms, intersections, vector addition and subtraction, cross products. An identity function, which will compare two tuples with different numerical values represent the same half-space and see if they’re the same onject. A few “maintenance” operators that will rearrange the numerical representation of an object in what might be more “tidy” form (expanding points away from zero and shrinking them down from infinity; centering them; that sort of thing).

The evolving algorithms will be able to perform operations in several dimensions, using a transparent mechanism. They have access to a stack containing, say, points of different cardinality. When they try to AddPoint, they’ll pop the top point off the stack, determine its dimension, and then pull the next point of that same dimension; add the two, and push the result back onto the stack. Lacking a second point, the operation fails gracefully, replacing the original point to the top of the stack.

What you’ve done, I think, allows me to work with these half-spaces as easily. So a hypothetical PointInHalfSpace? function might pop the top point, and the topmost half-space of that cardinality, and push a boolean that states whether the point lies within the half-space.

So — thanks again!

Maynard Handley said,

December 2, 2005 @ 7:34 pm

I’d add just one point to what people have said above.
What you *really* want in a situation like this is what’s called an orientation. An orientation is, in the most hand-waving terms, a rule that allows one to move from n-dimensions to n-1 dimensions in a consistent fashion. When, in the examples you give, you talk about “clock-wise” or “the right-hand-rule” you are implicitly using an orientation.
A volume form, as described by poster #4, implicitly defines an orientation, which is why what he is suggesting works.

If you want to be more formal about this, the buzzword you want to look for in a differential geometry book is the hodge dual (represented by the * operator) which performs exactly the operation you are describing.

Antonio said,

December 6, 2005 @ 4:45 pm

Oy vey. Exterior algebra and Hodge duality is all nice and good. But this just boils down to the determinant. You want those vectors X such that the matrix (B-A,C-A,D-A,X-A) has, say, nonnegative determinant.

RSS feed for comments on this post · TrackBack URI

Leave a Comment