Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions 


Emo Welzl 
Institut für Informatik
Freie Universität Berlin
email: emo@inf.fu-berlin.de
(joint work with L. Paul Chew, Klara Kedem, Micha Sharir and Boaz Tagansky)
Report B 95-06
April 1995 

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-95-06.ps.gz
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions The combinatorial complexity of the Voronoi diagram of $n$ lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be $\vorPPcompl$, where $\alpha$ is a slowly growing inverse of the Ackermann function. There are arrangements of $n$ lines where this complexity can be as large as $\Omega(n^2 \alpha(n))$.