Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl · Journal of Algorithms · 1998
The combinatorial complexity of the Voronoi diagram ofnlines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to beO(n2α(n)log n), where α(n) is a slowly growing inverse of the Ackermann function. There are arrangements ofnlines where this complexity can be as large as Ω(n2α(n)).