What is the worst-case complexity of a convex polytope with n vertices and n facets? Avis, Bremner, and Seidel refer to polytopes with asymptotically more faces than vertices and facets as intricate, fat-lattice, or just fat polytopes.The first interesting case is in four dimensions, where the problem was first posed by Kalai, Perles, and Stanley. Euler's formula implies an upper bound of O(n) for simple or simplicial polytopes (of any dimension), but perhaps pathological polytopes are more complex. A theorem of Edelsbrunner and Sharir, originally used to bound the maximum number of unit distances among a set of points in 3-space, implies an upper bound of O(n4/3). The only known lower bound in four dimensions is the trivial Omega(n). The best known construction, due to David Eppstein, has 5n-o(n) edges and ridges; Eppstein also constructed a family of 3-spheres (tilings of 3-space with convex polytopes) with 6n-o(n) edges and ridges, but these may not be realizable as polytopes. Are there fat-lattice polytopes in four dimensions?
Update (25 May 2000): Günter Zeigler defines the "fatness" of a 4-polytope as the ratio (f1+f2)/(f0+f3) where fi denotes the number of i-dimensional faces. Even 4-polytopes with larger constant fatness would be interesting. Ziegler recently observed that several recent conjectures on polytope flag vectors are disproved by examples of 4-polytopes with constant fatness, including the bicyclic polytopes of Smilanksy (fatness ~ 4), the neighborly cubical polytopes of Joswig and Ziegler (fatness ~ 5), and Eppstein's polytopes (fatness ~ 5) and 3-spheres (fatness ~ 6).
Up to constant factors, the problem is actually solved in five dimensions, thanks to the following recent observation of David Eppstein. The join of two polytopes P and Q of dimensions p and q, respectively, is obtained by embedding the polytopes in disjoint affine subspaces of (p+q+1)-dimensional space and taking their convex hull. For example, the join of two (1-dimensional) line segments is a (3-dimensional) tetrahedron. Eppstein observed that the join of two n/2-gons is a 5-dimensional polytope with n vertices, n facets, and n2 + 4n + 4 faces of all dimensions. Since a 5-polytope with n vertices has at most O(n2) faces, this is asymptotically optimal. Moreover, the join of two polygons is self-dual, and it can be realized as either a Voronoi diagram or a Delaunay complex in four dimensions!
Generalizing this construction to d dimensions gives us a lower bound of Omega(nfloor{(d+1)/3}), improving an earlier lower bound of roughly Omega(nsqrt{d/2}) due to Raimund Seidel based on products of cyclic 4-polytopes. (Joins of polygons are self-dual, inscribable, and circumscribable in all dimensions.) Unfortunately, the only known upper bound in dimensions higher than four is O(nfloor{d/2}), which follows immediately from the upper bound theorem for convex polytopes. Are joins of polygons optimal in dimensions six and higher? Can we achieve Omega(n3) faces in less than eight dimensions? Alternately, does an O(n2) upper bound hold in any dimension higher than five?
This problem arises in bounding the complexity of convex hull algorithms. Although worst-case optimal convex hull algorithms are known, these algorithms are not output-sensitive. In fact, the running time of any known convex hull algorithm can be exponentially larger than the combined input and output size. For example, many algorithms actually enumerate every face of the convex hull, rather than just listing the facets. Such an algorithm will perform quite badly when the convex hull is a fat-lattice polytope. See ``How Good are Convex Hull Algorithms?'' by David Avis, David Bremner, and Raimund Seidel, Computational Geometry: Theory and Applications 7(5-6):265-310, 1997. See also David Avis and Komei Fukuda's comments on the CG taskforce report, and Raimund Seidel's survey of convex hull algorithms in the recent CRC Handbook on Discrete and Computational Geometry.
A related question concerns the number of vertex/facet incidences in a convex polytope with n vertices and n facets. Euler's formula implies an optimal O(n) upper bound in two and three dimensions, and Eppstein's fat-lattice 5-polytope implies an optimal Omega(n2) lower bound in dimensions five and higher. Only the four-dimensional case is open. In this case, since each facet is a 3-polytope, Euler's formula implies that the number of vertex-facet incidences is asymptotically equal to the number of faces. Thus, the best known bounds are Omega(n) and O(n4/3).
Open Problems -
Jeff Erickson
(jeffe@cs.uiuc.edu)
25 May 2000