From: Daniel Harrison <Daniel.Harrison@durham.ac.uk>
Newsgroups: sci.math
Subject: intersection of plane and cube in 6-D
Date: 29 Aug 1997 10:05:06 GMT

If I have a cubic volume defined by

  l1 < x1 < u1,  l2 < x2 < u2, ..., l6 < x6 < u6

and a plane defined by

  a0 + a1x1 + x2x2 + ... + a6x6 = 0

how can I find the area of intersection?  Any references would be helpful.

Alternatively, how do I find the volume of an n-dimensional shape (n would
be 5 in this case) given points on its surface?

Thanks,

Dan.
(daniel.harrison@durham.ac.uk)

==============================================================================

From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: intersection of plane and cube in 6-D
Date: 6 Sep 1997 06:28:21 GMT

In article <5u66si$c2e$1@sirius.dur.ac.uk>,
Daniel Harrison  <Daniel.Harrison@durham.ac.uk> wrote:

>Alternatively, how do I find the volume of an n-dimensional shape (n would
>be 5 in this case) given points on its surface?

No one seems to be offering anything better so let me just point out
that what you seem to mean is that you have a finite set  S  of points
and you're looking for the  n-dimensional volume of its convex hull  C. If
P  is a point in the interior (for example,  P  could be the average of
the points in  S, or indeed could be any of the vertices in  S  itself)
then your set is the (essentially disjoint) union of a number of
simplices, namely the simplices formed by taking the cone at  P  of each
of the faces of the convex hull  C. The volume of each simplex is easy to
find (e.g. by computing a determinant). So really the only question is
to decide which sets of  n  elements of  S  are the vertices of the faces
of your region  C.  In the setting from which your question arose, that's
easy enough (the faces are the intersections of the one plane with the
planes on the face of the box). For the general case in which the set
S is an arbitrary finite set in Euclidean space, one uses convex-hull
algorithms, I guess, about which I know very little.

Actually I'm lying here just a little bit: the decomposition of your  C
won't really be into a union of  n-simplices unless the boundary
consists of  (n-1)-simplices. For example, to compute the volume of a
dodecahedron as above, we would describe it as the union of 12 cones on
the pentagonal faces. Those cones aren't really simplices, and so their
volume wouldn't be easily computed by determinants. Still, it's no big
deal to compute such volumes: the volume of an n-dimensional cone on a
(n-1)-dimensional measurable set  A  is 
	(1/n)*( (n-1)-measure of  A) * height
where the height is measured perpendicularly from the vertex of the cone
to the flat containing  A. Fortunately this is no big deal in your setting:
if  A  lies in a side of the box given by an equation  x_i = c, this
height is just  |c-p_i|,  where  p_i  is the i-th coordinate of the
vertex  P  of the cone. 

You can of course compute the other factor  ((n-1)-measure of  A)  by the same
procedure, giving you a recursive method of finding  n-volumes for all n.

It seems to me that there aren't too many combinatorial types for the
possible intersections of a box and a plane -- simplices, prisms, and so on --
and so a smarter algorithm for your specific problem probably exists
(classify the shape, measure a couple of dimensions, apply formulas for
volumes of simplices, frusta, and products) but I don't have the details 
sorted out.

dave

==============================================================================

Date: Sun, 7 Sep 1997 00:14:04 -0500 (CDT)
From: Dave Rusin <rusin>
To: Daniel.Harrison@durham.ac.uk
Subject: Re:  intersection of plane and cube in 6-D

I was a little hasty in my post. If you want to compute the height of a
"cone", you take a vector from the base to the cone vertex  P  and 
find out how long its projection is when projected to the orthogonal
complement of the base. _If_ the figure is n-dimensional _and_ in  R^n,
that orthogonal complement is just a line, and you can compute the
height as I said. But in your setting the figure will be in  R^(n+1)  at
least, so finding the height is just a little more involved.

You should probably ignore my suggestions to classify the various types
of intersections and find volumes directly. Even in the easy case
of the intersection of a plane and a box in R^3, the possible intersections
are polygons with  3, 4, 5, or 6   sides, so finding the area isn't
altogether simple. There are dozens of types of polyhedral which can be
the intersection of a plane and box in  R^4. I won't even think about
the case of  R^6. You're better off finding the volume as I said --
subdividing into small simplexes

dave