Name
Title | ||
|---|---|---|
A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D |
Abstract | ||
|---|---|---|
We consider the Voronoi diagram of a set of n points in three dimensions under a convex distance function induced by an arbitrary, fixed polytope. The combinatorial complexity, i.\,e.\ the number of vertices, edges, and facets, of this diagram is shown to be in &thgr;(n^2), which constitutes a considerable improvement to the results known so far.Unlike previous work, we do not need probabilistic arguments or recurrence techniques, but we exploit properties of the involved geometric structures. Key observations are that the lower envelope of n polygonal chains in the plane with a total of O(n) line segments and with only a fixed number of slopes is linear in~n, and that the number of slopes of Voronoi edges is bounded by a constant that only depends on the complexity of the polytope. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/380752.380815 | STOC |
Keywords | Field | DocType |
voronoi edge,fixed polytope,polyhedral convex distance function,combinatorial complexity,n point,convex distance,involved geometric structure,n polygonal chain,voroni diagram,fixed number,considerable improvement,voronoi diagram,polyhedron,convex polytope,complexity,bisector,three dimensions,distance function | Discrete mathematics,Power diagram,Combinatorics,Vertex (geometry),Polyhedron,Convex hull,Polytope,Convex polytope,Weighted Voronoi diagram,Voronoi diagram,Mathematics | Conference |
ISBN | Citations | PageRank |
1-58113-349-9 | 5 | 0.49 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Icking | 1 | 364 | 33.17 |
| Lihong Ha | 2 | 5 | 0.49 |