(sorry, may have accidentally sent you a junk email, here comes the real one) LOVELY DUALITY (Rupert/Trepur?) THEOREM: A convex polytope in D dimensions, is centrally linearly Rupertable, if and only if its dual polytope is. Furthermore, the max-allowed expansion factors are equal, and the rotation matrices identical. DEFINITIONS: "convex polytope" = a compact set of nonzero D-volume that is an intersection of halfspaces. (Usual use assumes a finite number of halfspaces, but these theorems will not require that.) A convex polytope is "centrally linearly rupertable" = a rotated copied version of it can be passed thru a hole drilled thru it, where the motion is translation along a line and the two centers of mass coincide at some moment during the motion. The rotated copied version can still be passed thru even if scaled by factor E>=1, then we can consider the supremum of all allowed E, that's the "max expansion factor." If a convex polytope is the intersection of halfspaces x.v<=1 for various v, then the "dual" polytope is the convex hull of those vectors v, (the v are its vertices). Note this "duality" notion has also been called "polar" or "geometric reciprocation." The dual of a convex object is always another. The dual dual of a convex polytope is the original polytope back again (a fairly famous theorem whose proof is a short exercise in linear algebra) provided that (0,0,0,...,0) lies inside the original polytope. PROOF OF OUR THEOREM: Notation: let TruncIdent(m,n) mean the nXn diagonal matrix with first m diagonal entries all 1, remaining entries all 0. Let Pr be a matrix whose columns are the vertices of the primal polytope with center of mass (0,0,0,...,0). Let Du be a matrix whose columns are the vertices of the dual polytope. We are going to ASSUME that the origin (0,0,0,...0) is the crux point for Rupertability -- that is, if the moving rotated copy of Pr clearly lies inside a straight tunnel drilled thru P AT THE MOMENT both centerpoints coincide at (0,0,0,...,0) then it is Rupertable. This assumption seems valid if we are considering centrosymmetric Pr (and hence Du). But for non-centrosymmetric polytopes, most notably the regular simplex, the best Rupertization probably never features the two centers of mass coinciding. However, the argument we shall give actually is valid if the origin is ANY interior point of Pr, NOT necessarily the center of mass, provided we are considering only motions which cause the origin for Pr, to coincide with the origin for Du, at some one moment, and this moment is crux. So: We claim Pr is linearly rupertable if and only if there exists two DxD orthogonal matrices (a real square matrix is "orthogonal" if its transpose equals its inverse) Q1 and Q2 such that all entries of M = Du^T Q2^T TruncIdent(D-1,D) Q1 Pr (where Z^T denotes the transpose of matrix Z) are less than 1. Indeed, the max allowed expansion factor equals the reciprocal of M's maximum entry. This formalizes the idea that the orthogonal projection of Pr (after rotation by Q1) into the first D-1 dimensions, fits inside a copy of Pr rotated by Q2. Once you see that, then note that M^T = Pr^T Q1^T TruncIdent(D-1,D) Q2 Du which is the SAME THING except Pr and Du (and Q1 and Q2) interchanged! Since the entries of M and M^T are the same, Pr is linearly centrally rupertable iff Du is -- and the expansion factors, and rotation matrices Q1,Q2, are the same. QED. So, this seems to be a beautiful theorem. There are, however, some assumptions lurking around behind the scenes in the present argument and theorem statement, which it might be nice to clean up a bit. Hopefully my computer will soon start using this theorem to seek Rupertings for all the regular polytopes... (PS. I now also have a proof the regular simplex is Rupertable in all dimensions.) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)