A semidynamic construction of higher-order voronoi diagrams and its randomized analysis
作者： Jean -Daniel Boissonnat , Olivier Devillers , Monique Teillaud
DOI: 10.1007/BF01228508
关键词: Combinatorics 、 Tree (descriptive set theory) 、 Centroidal Voronoi tessellation 、 Delaunay triangulation 、 Weighted Voronoi diagram 、 Dimension (graph theory) 、 Power diagram 、 Voronoi diagram 、 Asymptotically optimal algorithm 、 Mathematics 、 Discrete mathematics
摘要: Thek-Delaunay tree extends the Delaunay introduced in [1], and [2]. It is a hierarchical data structure that allows semidynamic construction of higher-order Voronoi diagrams finite set ofn points any dimension. In this paper we prove randomized thek-Delaunay tree, thus all order≤k diagrams, can be done inO(n logn+k 3n) expected time O(k2n) storage plane, which asymptotically optimal for fixedk. Our algorithm tod-dimensional space with complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The simple experimental results are given.
springer.com
sci-hub.se 参考文章(18)
P. J. Green, R. Sibson, Computing Dirichlet Tessellations in the Plane The Computer Journal. ,vol. 21, pp. 168- 173 ,(1978) , 10.1093/COMJNL/21.2.168
K. Mulmuley, On obstructions in relation to a fixed viewpoint foundations of computer science. pp. 592- 597 ,(1989) , 10.1109/SFCS.1989.63540
Michael Ian Shamos, Dan Hoey, Closest-point problems foundations of computer science. pp. 151- 162 ,(1975) , 10.1109/SFCS.1975.8
Bernard Chazelle, Herbert Edelsbrunner, An improved algorithm for constructing kth-order Voronoi diagrams symposium on computational geometry. pp. 228- 234 ,(1985) , 10.1145/323233.323263
J D Boissonnat, M Teillaud, The hierarchical representation of objects: the Delaunay tree Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 260- 268 ,(1986) , 10.1145/10515.10543
Leonidas J. Guibas, Donald E. Knuth, Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams Algorithmica. ,vol. 7, pp. 381- 413 ,(1992) , 10.1007/BF01758770
K. L. Clarkson, Applications of random sampling in computational geometry, II symposium on computational geometry. ,vol. 4, pp. 1- 11 ,(1988) , 10.1145/73393.73394
Jean-Daniel Boissonnat, Olivier Devillers, René Schott, Monique Teillaud, Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry Discrete and Computational Geometry. ,vol. 8, pp. 51- 71 ,(1992) , 10.1007/BF02293035
K. Mehlhorn, St. Meiser, C. Ó'Dúnlaing, On the construction of abstract voronoi diagrams Discrete & Computational Geometry. ,vol. 6, pp. 211- 224 ,(1991) , 10.1007/BF02574686
Kenneth L. Clarkson, New applications of random sampling in computational geometry Discrete & Computational Geometry. ,vol. 2, pp. 195- 222 ,(1987) , 10.1007/BF02187879