✦ LIBER ✦
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
✍ Scribed by L.Paul Chew; Klara Kedem; Micha Sharir; Boaz Tagansky; Emo Welzl
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 261 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 arrangements of n lines where this Ž 2 Ž .. complexity can be as large as ⍀ n ␣ n .