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