Name
Abstract | ||
|---|---|---|
We analyze structural properties of the order-k Voronoi diagram of line segments, which surprisingly has not received any attention in the computational geometry literature. We show that order-k Voronoi regions of line segments may be disconnected; in fact a single order-k Voronoi region may consist of Omega(n) disjoint faces. Nevertheless, the structural complexity of the order-k Voronoi diagram of non-intersecting segments remains O(k(n -k)) similarly to points. For intersecting line segments the structural complexity remains O(k(n -k)) for k >= n/2. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-35261-4_21 | ALGORITHMS AND COMPUTATION, ISAAC 2012 |
Keywords | Field | DocType |
computational geometry,Voronoi diagrams,line segments,higher order Voronoi diagrams | Discrete mathematics,Line segment,Power diagram,Combinatorics,Disjoint sets,Structural complexity,Computational geometry,Voronoi diagram,Line segment intersection,Mathematics | Conference |
Volume | ISSN | Citations |
7676 | 0302-9743 | 7 |
PageRank | References | Authors |
0.60 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evanthia Papadopoulou | 1 | 110 | 18.37 |
| Maksym Zavershynskyi | 2 | 21 | 2.31 |