Open Combinatorial Problems

Call a facet of a d-dimensional polytope degenerate if it has more than d vertices. How many degenerate facets can an n-vertex polytope have, in the worst case?

An upper bound of O(n^floor{d/2}) is trivial, since there are at most that many facets. I can construct examples with Omega(n^{ceiling{d/2}-1}) degenerate facets by taking the convex hulls of certain integer points on the polynomial curve w(t) = (t, t², t³, ..., t^d-1, t^d+1), which I dubbed the "weird moment curve". These two bounds match in odd dimensions, but there is still a gap when the dimension is even. In particular, in four dimensions, the upper bound is O(n²), but the best lower bound is only Omega(n).

The best four-dimensional construction I know of is the connected sum of n/5 - 1 copies of a bipyramid over a cube, which has n vertices and 2n-8 facets, each a square pyramid. Is there a 4-polytope with even 2n degenerate facets?

I am particularly interested in the case of quasisimplicial polytopes, each of whose (d-2)-faces is a simplex. The weird moment curve examples are quasisimplicial.

Update (09 Nov 1999): Michael Joswig and Günter Ziegler recently introduced the class of neighborly cubical polytopes -- n-vertex d-dimensional polytopes whose every facet is a combinatorial hypercube and whose r-skeletons are combinatorially equivalent to those of higher-dimensional hypercubes. Joswig and Zeigler show that neighborly cubical polytopes exist whenever n > d > 2r+2. In particular, a 4-dimensional neighborly cubical polytope has Omega(n log n) cubical (and therefore degenerate) facets.

I still believe that the lower bound is closer to the truth than the upper bound.

Given a set of n points and m hyperplanes in R^d, consider the induced bipartite incidence graph, where a point node is connected to a hyperplane node if and only if the point lies on the hyperplane. Suppose this graph has no s × t complete bipartite subgraph; that is, no s points all lie on the same t hyperplanes. How many edges can this graph have in the worst case? (If we don't put any restrictions on the incidence graph, there can be mn indicences in dimensions 3 and higher.)

The following table summarizes some of what's known. The upper bounds follow from the techniques in "Combinatorial complexity bounds for arrangements of curves and spheres", by Clarkson, Edelsbrunner, Guibas, Sharir, and Welzl, Discrete & Computational Geometry 5:99-160, 1990. The lower bounds follow from a well-known construction of Paul Erdös and some higher-dimensional generalizations of it that I discovered.

A particularly interesting case is when n=m and s=t=d. In this case, the best bounds are O(n^2d/(d+1)) and Omega(n^4/3). I believe the upper bound is tight.

Another interesting special case is when the points are required to be vertices of the arrangement of the hyperplanes. In this case, Pankaj Agarwal and Boris Aronov proved a tight bound of Theta(m^2/3n^d/3 + n^d-1).

What is the worst-case complexity of the union of n intersecting unit balls in 3-space? The best known bounds are Omega(n) and O(n²).

If we do not require the balls to have a common intersection, then the union can have quadratic complexity. If we allow the balls to have two different radii, their union can have quadratic complexity. The bottleneck in generalizing these two constructions is that if two unit spheres contain each other's centers (as is the case if all the spheres are centered close to the origin), then one sphere contains at least 1/4 of the surface area of the other sphere. On the other hand, the intersection of unit balls always has linear complexity.

Olivier Devillers has suggested that perhaps results from the following paper can be used to derive an almost linear upper bound:

J. T. Schwartz and M. Sharir. "On the two-dimensional Davenport- Schinzel problem". J. Symbolic Comput. 10:371-393, 1990.

Olivier has a Web page listing other results and open problems related to the complexity of unions, intersections, and convex hulls of spheres.

Update (09 Nov 1999): This problem was independently solved by several people. The solution was first published in the XXX archive by Hervé Brönnimann and Olivier Devillers, but exactly the same solution was communicated to me a year earlier by Kasturi Varadarajan. Brönnimann and Devillers indicate that Alon Efrat may have also found a solution.

Line traversals of Delaunay triangulations [Nina Amenta] - Solved!

In their paper "Deformed products and maximal shadows", Nina Amenta and Günter Ziegler showed that a 2-dimensional slice of a d-dimensional n-vertex convex polytope can have Omega(n^floor{d/2}) facets - as many as the original polytope. This bound is tight, since the original polytope has at most O(n^floor{d/2}) facets.

Since every d-dimensional polytope corresponds to a (d-1)-dimensional regular triangulation, this means that some 3-dimensional regular triangulations admit a line traversal through Omega(n²) of their cells. Is this also true for Delaunay triangulations? Equivalently, do the slice lower bounds hold for polytopes whose vertices are cospherical? (Somewhat surprisingly, the lower bounds are not acheived by slices of cyclic polytopes.)

Update (18 Oct 1999): This problem was solved by Jonahan Shewchuk. His solution is to slightly perturb a set of points n on two skew lines x=0,y=0 and y=1,z=0, with n/2 evenly-spaced point on each line. The resulting Delaunay triangulation has Omega(n²) tetrahedra, n²/4 of which can be stabbed by a single line. His construction generalizes easily to higher dimensions. See Shewchuk's solution for more details.

There are three kinds of mathematicians:
those who can count, and those who can't.

- folklore

1. Three words: bad counting.

- from "Top Ten Signs Your Top Ten List Sucks"
Late Show with David Letterman, April 22, 1998

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 09 Nov 1999