Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks
- Title
- Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks
- Author
- 김덕수
- Keywords
- Algorithms; Theory; Additively-weighted Voronoi diagram; disks; quasi-triangulation; betacomplex; simplex; simplicial complex; topology
- Issue Date
- 2016-05
- Publisher
- ASSOC COMPUTING MACHINERY
- Citation
- ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, v. 43, NO 2, Page. 1-23
- 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 R-2 and spherical balls in R-3 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.
- URI
- https://dl.acm.org/citation.cfm?doid=2988256.2939366https://repository.hanyang.ac.kr/handle/20.500.11754/70331
- ISSN
- 0098-3500; 1557-7295
- DOI
- 10.1145/2939366
- Appears in Collections:
- COLLEGE OF ENGINEERING[S](공과대학) > MECHANICAL ENGINEERING(기계공학부) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML