Voronoi Diagrams of Lines in 3-Space Und
✍
L.Paul Chew; Klara Kedem; Micha Sharir; Boaz Tagansky; Emo Welzl
📂
Article
📅
1998
🏛
Elsevier Science
🌐
English
⚖ 261 KB
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 Ž 2 Ž . . Ž . number of edges is shown to be O n ␣ n log n , where ␣ n is a slowly growing inverse of the Ackermann function. There are arrangemen