What is the worst-case complexity of a convex polytope withAvis, Bremner, and Seidel refer to polytopes with asymptotically more faces than vertices and facets asnvertices andnfacets?intricate,fat-lattice, or justfatpolytopes.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 ofO(n. The only known lower bound in four dimensions is the trivial^{4/3})Omega(n). The best known construction, due to David Eppstein, has5n-o(n)edges and ridges; Eppstein also constructed a family of 3-spheres (tilings of 3-space with convex polytopes) with6n-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 (f_{1}+f_{2})/(f_{0}+f_{3}) wherefdenotes the number of_{i}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

joinof two polytopesPandQof dimensionspandq, 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 twon/2-gons is a 5-dimensional polytope withnvertices,nfacets, andnfaces of all dimensions. Since a 5-polytope with^{2}+ 4n + 4nvertices has at mostO(nfaces, 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!^{2})Generalizing this construction to

ddimensions gives us a lower bound ofOmega(n, improving an earlier lower bound of roughly^{floor{(d+1)/3}})Omega(ndue 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^{sqrt{d/2}})O(n, which follows immediately from the upper bound theorem for convex polytopes.^{floor{d/2}})Are joins of polygons optimal in dimensions six and higher? Can we achieveOmega(nfaces in less than eight dimensions? Alternately, does an^{3})O(nupper bound hold in any dimension higher than five?^{2})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

faceof the convex hull, rather than just listing thefacets. 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

nvertices andnfacets. Euler's formula implies an optimalO(n)upper bound in two and three dimensions, and Eppstein's fat-lattice 5-polytope implies an optimalOmega(nlower 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^{2})Omega(n)andO(n.^{4/3})

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 25 May 2000