Robust Construction of the Additively-Weighted Voronoi Diagram via Topology-Oriented Incremental Algorithm
Voronoi diagrams tessellate the space where each cell corresponds to an associated generator under an a priori defined distance and have been extensively used to solve geometric problems of various disciplines. Additively-weighted Voronoi diagrams, also c
- PDF / 1,004,524 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 219 Views
School of Mechanical Engineering, Hanyang University, Seoul, Korea [email protected], [email protected] 2 Meiji University, Tokyo, Japan [email protected] http://voronoi.hanyang.ac.kr, http://home.mims.meiji.ac.jp/∼sugihara/Welcomee.html
Abstract. Voronoi diagrams tessellate the space where each cell corresponds to an associated generator under an a priori defined distance and have been extensively used to solve geometric problems of various disciplines. Additively-weighted Voronoi diagrams, also called the Voronoi diagram of disks and spheres, have many critical applications and a few algorithms are known. However, algorithmic robustness remains a major hurdle to use these Voronoi diagrams in practice. There are two important yet different approaches to design robust algorithms: the exactcomputation and topology-oriented approaches. The former uses highprecision arithmetic and guarantees the correctness mathematically with the cost of a significant use of computational resources. The latter focuses on topological properties to keep consistency using logical computation rather than numerical computation. In this paper, we present a robust and efficient algorithm for computing the Voronoi diagram of disks using a topology-oriented incremental method. The algorithm is rather simple as it primarily checks topological changes only during each disk is incrementally inserted into a previously constructed Voronoi diagram of some other disks. Keywords: Topology-oriented · Additively-weighted diagram · Disk · Circle · Robustness · Algorithm
1
·
Voronoi
Introduction
The Voronoi diagram is a tessellation of space where each element of the tessellation is associated with a generating particle. The ordinary Voronoi diagram VD of a set of points P = {p1 , p2 , . . . , pn }, pi ∈ Rd , is the tessellation so that the Voronoi cell of pi ∈ P is the set of locations closer to pi than to pj ∈ P , i = j for a given distance definition [1,2]. Suppose that pi ∈ P is assigned w w w a weight wi ≥ 0. In other words, P w = {pw 1 , p2 , · · · , pn } where pi = (pi , wi ). c Springer International Publishing Switzerland 2016 G.-M. Greuel et al. (Eds.): ICMS 2016, LNCS 9725, pp. 514–521, 2016. DOI: 10.1007/978-3-319-42432-3 66
Robust Construction of the Additively-Weighted Voronoi Diagram
515
Then, the power diagram can be similarly defined with the power distance which is defined as dist(x, pi )2 − wi , where dist() denotes the Euclidean distance function. Let D = {d1 , d2 , . . . , dn } be a set of disks where di = (pi , ri ) is a disk with the center pi and radius ri . Let VC(di ) denote the V-cell of di defined as VC(di ) = {x ∈ Rd | dist(x, pi ) − ri ≤ dist(x, pj ) − rj , i = j}. Then, the Voronoi diagram of disks D is defined as VD(D) = {VC(d1 ), VC(d2 ), · · · , VC(dn )} which is also frequently called the additively-weighted Voronoi diagram. It turns out , w ) corresponds to a disk di = (pi , ri ) with the center pi and the that pw i = (p √i i radius ri = wi . Then, dist(x, pi )2 − ri2 is the square of the tangential
Data Loading...
