Name
Abstract | ||
|---|---|---|
The order- Voronoi diagram of line segments has properties surprisingly different from its counterpart for points. For example, a single order- Voronoi region may consist of disjoint faces. In this paper, we analyze the structural properties of this diagram and show that its combinatorial complexity is , for non-crossing line segments, despite the presence of disconnected regions. The same bound holds for intersecting line segments, for . We also consider the order- Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order- diagram to cover sites that are not disjoint. On the algorithmic side, we extend the iterative approach to construct this diagram, handling complications caused by the presence of disconnected regions. All bounds are valid in the general metric, . For non-crossing segments in the and metrics, we show a tighter bound for . |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-014-9950-0 | Algorithmica |
Keywords | Field | DocType |
Computational geometry,Voronoi diagram,Line segments,Planar straight line graph,Order-,k,Voronoi diagram,\(k\),nearest neighbors,\(L_p\),metric | Line segment,Power diagram,Discrete mathematics,Combinatorics,Disjoint sets,Planar straight-line graph,Diagram,Voronoi diagram,Weighted Voronoi diagram,Line segment intersection,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1405.3806 | 1 | 0178-4617 |
Citations | PageRank | References |
2 | 0.38 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evanthia Papadopoulou | 1 | 110 | 18.37 |
| Maksym Zavershynskyi | 2 | 21 | 2.31 |