| Autor: |
Lee, Mokwon, Sugihara, Kokichi, Kim, Deok-Soo |
| Předmět: |
|
| Zdroj: |
ACM Transactions on Mathematical Software; Aug2016, Vol. 43 Issue 2, p1-23, 23p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
