Call a facet of ad-dimensional polytopedegenerateif it has more thandvertices. How many degenerate facets can ann-vertex polytope have, in the worst case?An upper bound of

O(nis trivial, since there are at most that many facets. I can construct examples with^{floor{d/2}})Omega(ndegenerate facets by taking the convex hulls of certain integer points on the polynomial curve^{ceiling{d/2}-1})w(t) = (t,t^{2},t^{3}, ...,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 isO(n, but the best lower bound is only^{2})Omega(n).The best four-dimensional construction I know of is the connected sum of

n/5 - 1copies of a bipyramid over a cube, which hasnvertices and2n-8facets, each a square pyramid. Is there a 4-polytope with even2ndegenerate facets?I am particularly interested in the case of

quasisimplicialpolytopes, 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-vertexd-dimensional polytopes whose every facet is a combinatorial hypercube and whoser-skeletons are combinatorially equivalent to those of higher-dimensional hypercubes. Joswig and Zeigler show that neighborly cubical polytopes exist whenever. In particular, a 4-dimensional neighborly cubical polytope has n>d>2r+2Omega( cubical (and therefore degenerate) facets.nlogn)I still believe that the lower bound is closer to the truth than the upper bound.

Given a set ofnpoints andmhyperplanes in, 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 noR^{d}s × tcomplete bipartite subgraph; that is, nospoints all lie on the samethyperplanes. How many edges can this graph have in the worst case? (If we don't put any restrictions on the incidence graph, there can bemnindicences 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.

d | s | t | Upper bound | Lower bound |
---|---|---|---|---|

d | 1 | 1+ | O(n+m) [trivial] |
Omega(n+m) [trivial] |

2 | [2] | [2] | O(n + n^{2/3} m^{2/3} + m)
[Szemerédi/Trotter, Clarkson et al., Székely] |
Omega(n + n^{2/3} m^{2/3} + m)
[Erdös] |

3 | 2 | 3 | O(n + n^{4/5} m^{3/5} + m)
[Clarkson et al., Guibas/Overmars/Robert] |
Omega(n + n^{5/6} m^{1/2} + m)
[Erickson] |

3 | 3 | 3 | O(n + n^{3/4} m^{3/4} + m)
[Clarkson et al.] |
Omega(n + n^{5/6} m^{1/2} + m)
[Erickson] |

d | 2 | d | O(n + n^{(2d-2)/(2d-1)} m^{d/(2d-1)} + m)
[Clarkson et al., Guibas/Overmars/Robert] |
Omega(n + n^{1 - 2/d(d+1)} m^{2/(d+1)} + m)
[Erickson] |

d | d | d | O(n + n^{d/(d+1)} m^{d/(d+1)} + m)
[Clarkson et al.] |
Omega(n + n^{1 - 2/d(d+1)} m^{2/(d+1)} + m)
[Erickson] |

A particularly interesting case is whenn=mands=t=d. In this case, the best bounds areO(nand^{2d/(d+1)})Omega(n. I believe the upper bound is tight.^{4/3})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/3}n^{d/3}+ n^{d-1})

What is the worst-case complexity of the union ofnintersecting unit balls in 3-space? The best known bounds areOmega(n)andO(n.^{2})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

intersectionof 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.

In their paper "Deformed products and maximal shadows", Nina Amenta and Günter Ziegler showed that a 2-dimensional slice of ad-dimensionaln-vertex convex polytope can haveOmega(nfacets - as many as the original polytope. This bound is tight, since the original polytope has at most^{floor{d/2}})O(nfacets.^{floor{d/2}})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 throughOmega(nof 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^{2})notacheived 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 pointsnon two skew linesx=0,y=0 andy=1,z=0, withn/2 evenly-spaced point on each line. The resulting Delaunay triangulation has Omega(n^{2}) tetrahedra,n^{2}/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.

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