Polyhedral Voronoi diagrams of polyhedra in three dimensions
Vladlen Koltun, Micha Sharir · 2002
We show that that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in 3-space that have n vertices overall, under a convex distance function induced by a polyhedron with O(1) facets, is O(n 2+ε), for any ε>0. We also show that when the sites are n segments in 3-space, this complexity is O(n 2 α(n) log n). This generalizes previous results by Chew et al. [9] and by Aronov and Sharir [4], and solves an open problem put forward by Agarwal and Sharir [2]. Specific distance functions for which our results hold are the L 1 and the L ∞ metrics. These results imply that we can preprocess a collection of polyhedra as above into a near-quadratic data structure that can answer δ-approximate Euclidean nearest-neighbor queries amidst the polyhedra in time O(log (n/δ)), for an arbitrarily small δ>0.