For a polyhedron @math P let @math B(P) denote the polytopal complex that is formed by all bounded faces of @math P. If @math P is the intersection of @math n halfspaces in @math RD, but the maximum dimension @math d of any face in @math B(P) is much smaller, we show that the combinatorial complexity of @math P cannot be too high; in particular, that it is independent of @math D. We show that the number of vertices of @math P is @math O(nd) and the total number of bounded faces of the polyhedron is @math O(nd2). For inputs in general position the number of bounded faces is @math O(nd). We show that for certain specific values of @math d and @math D, our bounds are tight. For any fixed @math d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a number of linear programs that is polynomial in @math n.
Our results can also be interpreted as statements about the complexity of Delaunay triangulations for inputs satisfying strong convex position assumptions. Delaunay triangulations are closely related to convex hulls: the Delaunay triangulation is combinatorially equivalent to the convex hull of a point set lifted to a sphere in one higher dimension, augmented by an extra point at the pole of the sphere, followed by the removal of all faces incident to that pole @cite_3 . If a @math -dimensional set of @math points has the property that every interior point of the convex hull of the set belongs to a Delaunay triangulation feature of dimension at least @math , then our results imply via this lifting relation that the Delaunay triangulation has @math @math -dimensional simplices. For instance, if the convex hull of a point set is a stacked polytope (a convex figure formed by gluing simplices facet-to-facet) and the Delaunay triangulation coincides with the gluing pattern of the simplices, then every interior point of the convex hull belongs either to one of the simplices or to one of the glued facets, so @math ; in this case, the number of simplices in the Delaunay triangulation is exactly @math .
@cite_3
1984406695
The problem of construction of planar Voronoi diagrams arises in many areas, one of the most important of which is in nearest neighbor problems. This includes clustering [ 141, contour maps [6] and (Euclidean) minimum spanning trees [23]. Shamos [22] gives several more applications. An JZ(N log N) time worst case lower bound can be shown for this problem by reducing it to sorting [2 11. The challenge is to construct an O(N log N) time algorithm. Shamos [213 and Shamos anti Hoey [23] describe an O(N log N) time divide-and-conquer algorithm for construction of the planar Euclidean Voronoi diagram. Lee and Wong [ 161 describe an O(N log N) time algorithm for the L1 and L, metrics in the plane, and Drysdale pnd Lee [8] present an O(N@g N)l *) t’ rme algorithm for the Voronoi diagram of N line segments (which they have since improved to O(N(log N)*) time). Shamos [2 11, Lee and Preparata [ 151, and Lipton and Tarjan [ 171 have produced fast algorithms for searching a Voronoi diagram (or any other straight-line planar graph). In this paper we describe an O(N log N) time algorithm for constructing a planar Euclidean Voronoi diagram which extends straightforwardly to higher dimensions. The fundamental result is that a K-dimensional Euclidean Voronoi diagram of N points can be constructed by transforming the points to K + I-space,