Terminology
Most of this terminology is fairly standard, and you may only need to skim
this section. But do read my definitions of the terms dim(P)
and D(P) for a polytope P because these are referred
to frequently in the rest of the paper.
R^n:
The usual n-dimensional vector space over the field of real numbers.
The first four coordinates have traditionally been called, x, y, z, and w.
R^n will also be called "n-space".
Convex:
A subset of R^n is called convex if given any two points in the set, the line segment between those two points is also contained by the set. A sphere is convex, as is a triangle, as is R^n.
Polytopes and Faces:
Polytopes are the generalization of polygons and polyhedra: a polygon
is a two dimensional polytope; a polyhedron is a three dimensional
polytope. One dimensional polytopes are line segments; zero
dimensional polytopes are just points. The dimensionality of a
polytope is defined by the dimension of the volume it encloses.
"n-polytope" is short for "n dimensional polytope".
Formally, a convex n-polytope is a finite intersection of
closed half-spaces of R^n such that the intersection has finite
non-zero volume in R^n. An example of a closed half-space in R^2 is {
(x,y) | y >= 0 }. This half-space does not define a polytope
because the 2-d volume is not finite. The intersection of { (x,y) | y
>= 0 } with { (x,y) | y <= 0 } does not define a polytope because
the 2-d volume is zero. But the following closed half-spaces
intersect to form a square:
- { (x,y) | y >= 0}
- { (x,y) | y <= 1}
- { (x,y) | x >= 0}
- { (x,y) | x <= 1}
Non-convex polytopes can be expressed as connected unions of convex
polytopes of the same dimension.
For me, the important thing about polytopes is that the boundary, the
"skin", of an n-polytope is a collection of
(n-1)-polytopes. These (n-1)-polytopes are called the
faces of the n-polytope (note that faces need not be 2
dimensional, as they are in common usage of the term). For instance;
a hypercube's faces are 8 cubes; a cube's faces are 6 squares; a
square's faces are 4 line segments, a line segment's faces are two
vertices; vertices have no faces. Faces are themselves polytopes, and
often, a given polytope under consideration is in fact a face of some
other polytope, so in this report the terms "face" and "polytope" may
end up being used somewhat interchangeably.
(My use of the word "boundary" in the above agrees with the strict topological sense: An n dimensional polytope P is closed in R^n, being a finite intersection of closed half-spaces. So its boundary is P - Int P, where Int P is the interior of P, the union of all open sets contained in P).
k-subspace, k-flat:
"k-subspace" is short for "k dimensional subspace", which is the set of points spanned by k linearly independent vectors which lie in some other vector space which is known from context. A k-flat is any translation of a k-subspace. That is, the k-subspace must contain the origin of the vector space, the k-flat need not. So { (x,y,z) | y = x } is a 2-subspace of R^3; { (x,y,z) | y = x + 2 } is 2-flat in R^3.
dim(P); D(P):
Let P be some polytope.
dim(P) is simply the dimension of the polytope. To
define D(P) we need to give first fix coordinates for
each of the vertices of P and thereby give P some
position and orientation in R^n. Then let D(P) to be
the integer m such that P is contained in R^m and
is not contained by R^k for any k < m. One can see
that dim(P) <= D(P). Also, note that
unlike dim(P), D(P) is not is
property of the polytope. It is only a property of the polytope's
position and orientation; it tells us something about the dimension of
the space that the polytope occupies. Here's an illustration of how
D(P) and dim(P) can differ:
Projections:
Call a linear transformation T of R^n a projection if
- rank(T) = n - 1 (the image of R^n under T has dimension n-1)
- T^2 = T (applying the projection a second time does nothing new)
Let P be a polytope, let n = D(P). Then define a projection of P to be the image of P under some projection T of R^n. This is just a formal way of saying that a projection "squashes" the polytope one dimension lower, though retaining some of the face structure.
Strictly speaking, then, the perspective transformations used in converting a 3-d scene into a 2-d perspective rendering are not projections. Although these transformations are "linear" in the sense that lines in 3-space are mapped to lines on the screen, the transformation is not linear in the algebraic sense of T(a+b) = T(a) + T(b). Even so, it is reasonable to refer to such transformations as perspective projections.
Slices vs. Cross-sections:
(I am imposing a more specific meaning on these terms than they have normally, but I needed terms for these specific meanings, and "slice" and "cross-section" seemed as good as any.)
Cross-sections:
Let P be a polytope, let n = D(P). A cross-section of a P is the intersection of P with an (n-1)-flat. This intersection may be the null set. For convex polytopes, the cross-section can be formed as follows:
- intersect all the half-spaces of R^n with the (n-1)-flat
- intersect all the intersections from step 1.
Since the intersections formed in step 1 are either the whole (n-1)-flat, a half-space of R^(n-1), or the null set, it follows that the cross-section of a convex polytope is either the null set or another convex polytope. Some cross-sections of cubes are 4-gons:
Slices:
A slice is a generalization of a cross-section. Let P be a polytope, let n = D(P). A slice of P is the intersection of P with a k-flat for any k < n, not necessarily k = n-1. "k-slice" is short for "intersection with a k-flat". Here a 1-slice is being taken in a cube, resulting in a line segment:
(back to Contents)
(on to Data Structure)