A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS

被引:28
作者
Aurenhammer, Franz [1 ]
Schwarzkopf, Otfried [2 ]
机构
[1] Free Univ Berlin, Fachbereich Math, Inst Informat, Berlin 33, Germany
[2] Rijksuniv Utrecht, NL-3508 TB Utrecht, Netherlands
关键词
Higher-order Voronoi diagrams; geometric transforms; randomized incremental construction; lower bounds;
D O I
10.1142/S0218195992000214
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present a simple algorithm for maintaining order-k Voronoi diagrams in the plane. By using a duality transform that is of interest in its own right, we show that the insertion or deletion of a site involves little more than the construction of a single convex hull in three-space. In particular, the order-k Voronoi diagram for n sites can be computed in time O(nk(2) log n + nk log(3) n) and optimal space O(k(n - k)) by an on-line randomized incremental algorithm. The time bound can be improved by a logarithmic factor without losing much simplicity. For k >= log(2) n, this is optimal for a randomized incremental construction; we show that the expected number of structural changes during the construction is Theta(nk(2)). Finally, by going back to primal space, we obtain a dynamic data structure that supports k-nearest neighbor queries, insertions, and deletions in a planar set of sites. The structure promises easy implementation, exhibits a satisfactory expected performance, and occupies no more storage than the current order-k Voronoi diagram.
引用
收藏
页码:363 / 381
页数:19
相关论文
共 23 条
[1]  
AGARWAL PK, 1990, PROCEEDINGS OF THE SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY, P203, DOI 10.1145/98524.98567
[2]   A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON [J].
AGGARWAL, A ;
GUIBAS, LJ ;
SAXE, J ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :591-604
[3]   A NEW DUALITY RESULT CONCERNING VORONOI DIAGRAMS [J].
AURENHAMMER, F .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (03) :243-254
[4]   POWER DIAGRAMS - PROPERTIES, ALGORITHMS AND APPLICATIONS [J].
AURENHAMMER, F .
SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :78-96
[5]  
AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880
[6]  
Boissonnat J.-D., ALGORITHMIC IN PRESS
[7]   APPLICATIONS OF RANDOM SAMPLING TO ONLINE ALGORITHMS IN COMPUTATIONAL GEOMETRY [J].
BOISSONNAT, JD ;
DEVILLERS, O ;
SCHOTT, R ;
TEILLAUD, M ;
YVINEC, M .
DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 8 (01) :51-71
[8]  
Chazelle B., 1991, 2ND ANN ACM SIAM S D, P441
[9]   NEW APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY [J].
CLARKSON, KL .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :195-222
[10]  
CLARKSON KL, 1992, LECT NOTES COMPUT SC, V577, P463