Name
Title | ||
|---|---|---|
Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks. |
Abstract | ||
|---|---|---|
Voronoi diagrams are useful for spatial reasoning, and the robust and efficient construction of the ordinary Voronoi diagram of points is well known. However, its counterpart for circular disks in R2 and spherical balls in R3 remains a challenge. In this article, we propose a topology-oriented incremental algorithm which robustly and efficiently computes a Voronoi diagram by incrementing a new disk generator to an existing one. The key idea is to enforce the convexity of the Voronoi cell corresponding to the incrementing disk so that a simple variation of the algorithm for points proposed by Sugihara in 1992 can be applied. A benchmark using both random and degenerate disks shows that the proposed algorithm is superior to CGAL in both computational efficiency and algorithmic robustness. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2939366 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
Algorithms,Theory,Additively-weighted Voronoi diagram,disks,quasi-triangulation,betacomplex,simplex,simplicial complex,topology | Power diagram,Topology,Mathematical optimization,Bowyer–Watson algorithm,Centroidal Voronoi tessellation,Algorithm,Robustness (computer science),Lloyd's algorithm,Voronoi diagram,Weighted Voronoi diagram,Fortune's algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 2 | 0098-3500 |
Citations | PageRank | References |
2 | 0.35 | 36 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mokwon Lee | 1 | 11 | 4.55 |
| Kokichi Sugihara | 2 | 856 | 241.55 |
| Deok-Soo Kim | 3 | 633 | 59.12 |