Name
Abstract | ||
|---|---|---|
In this paper, we present a plane sweep algorithm for constructing the Voronoi diagram of a set of non-crossing line segments in 2D space using a distance metric induced by a regular k-gon and study the robustness of the algorithm. Following the algorithmic degree model [G. Liotta, F.P. Preparata, R. Tamassia, Robust proximity queries: an illustration of degree-driven algorithm design, SIAM J. Comput. 28 (3) (1998) 864-889], we show that the Voronoi diagram of a set of arbitrarily oriented segments can be constructed with degree 14 for certain k-gon metrics (e.g., k = 6, 8, 12). For rectilinear segments or segments with slope +1 or -1, the degree reduces to 2. The algorithm is easy to implement and finds applications in VLSI layout. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ipl.2005.10.009 | Inf. Process. Lett. |
Keywords | Field | DocType |
computational geometry,algorithmic degree,voronoi diagram,siam j. comput,plane sweep algorithm,certain k-gon metrics,vlsi layout,non-crossing line segment,g. liotta,regular k-gon,k-gon voronoi diagram construction,degree-driven algorithm design,algorithmic degree model,algorithm design,distance metric | Discrete mathematics,Power diagram,Combinatorics,Algorithm design,Bentley–Ottmann algorithm,Metric (mathematics),Weighted Voronoi diagram,Fortune's algorithm,Voronoi diagram,Mathematics,Sweep line algorithm | Journal |
Volume | Issue | ISSN |
97 | 4 | 0020-0190 |
Citations | PageRank | References |
2 | 0.38 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhenming Chen | 1 | 39 | 2.74 |
| Evanthia Papadopoulou | 2 | 110 | 18.37 |
| Jinhui Xu | 3 | 665 | 78.86 |