In:
ACM Transactions on Mathematical Software, Association for Computing Machinery (ACM), Vol. 43, No. 2 ( 2017-06-30), p. 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.
Type of Medium:
Online Resource
ISSN:
0098-3500
,
1557-7295
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2017
detail.hit.zdb_id:
2006421-4
detail.hit.zdb_id:
191812-6
Permalink