Order-k voronoi diagrams of sites with additive weights in the plane
作者： Harald Rosenberger
DOI: 10.1007/BF01759056
关键词: Discrete mathematics 、 Lloyd's algorithm 、 Mathematics 、 Fortune's algorithm 、 Power diagram 、 Centroidal Voronoi tessellation 、 Combinatorics 、 Voronoi diagram 、 Diagram 、 Mathematical diagram 、 Weighted Voronoi diagram
摘要: It is shown that the order-k Voronoi diagram of n sites with additive weights in plane has at most (4kź2)(nźk) vertices, (6kź3)(nźk) edges, and (2kź1)(nźitk) + 1 regions. These bounds are approximately same as ones known for unweighted diagrams. Furthermore, tight upper on number edges vertices given case every weighted site a nonempty region order-1 diagram. The proof based new algorithm construction these diagrams which generalizes plane-sweep developed by Steven Fortune. time-complexityO(k2n logn) space-complexityO(kn). only nontrivial constructing order-kc withadditive weights. fairly simple practical interest also special sites.
springer.com
sci-hub.se 参考文章(12)
H. Edelsbrunner, N. Hasan, R. Seidel, X.J. Shen, CIRCLES THROUGH TWO POINTS THAT ALWAYS ENCLOSE MANY POINTS Geometriae Dedicata. ,vol. 32, pp. 1- 12 ,(1989) , 10.1007/BF00181432
Der-Tsai Lee, Robert L Drysdale, III, Generalization of Voronoi Diagrams in the Plane SIAM Journal on Computing. ,vol. 10, pp. 73- 87 ,(1981) , 10.1137/0210006
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
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
Leonidas Guibas, Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi ACM Transactions on Graphics. ,vol. 4, pp. 74- 123 ,(1985) , 10.1145/282918.282923
H. Edelsbrunner, E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms symposium on computational geometry. pp. 118- 133 ,(1988) , 10.1145/73393.73406
S Fortune, A sweepline algorithm for Voronoi diagrams Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 313- 322 ,(1986) , 10.1145/10515.10549
Der-Tsai Lee, On k-Nearest Neighbor Voronoi Diagrams in the Plane IEEE Transactions on Computers. ,vol. 31, pp. 478- 487 ,(1982) , 10.1109/TC.1982.1676031
Lee, Silio, An Optimal Illumination Region Algorithm for Convex Polygons IEEE Transactions on Computers. ,vol. 31, pp. 1225- 1227 ,(1982) , 10.1109/TC.1982.1675946
H. Edelsbrunner, Edge-skeletons in arrangements with applications Algorithmica. ,vol. 1, pp. 93- 109 ,(1986) , 10.1007/BF01840438