|
|||||
|
|
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions |
|
| Authors: | LPaul Chew Klara Kedem Micha Sharir Boaz Tagansky Emo Welzl |
| Institution: | aDepartment of Computer Science, Cornell University, Ithaca, New York, 14853;bDepartment of Mathematics and Computer Science, Ben Gurion University, Beer-Sheva, 84105, Israel;cSchool of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel;dCourant Institute of Mathematical Sciences, New York University, New York, New York, 10012;eSchool of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel;fInstitut für Theoretische Informatik ETH Zurich, IFW C4-8092, Zurich, Switzerland |
| Abstract: | 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)). |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |