A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D
Christian Icking, Lihong Ha · 2001
We consider the Voronoi diagram of a set of n points in three dimensions under a convex distance function induced by an arbitrary, fixed polytope. The combinatorial complexity, i.\,e.\ the number of vertices, edges, and facets, of this diagram is shown to be in θ(n^2), which constitutes a considerable improvement to the results known so far.