Dynamic construction of abstract Voronoi diagrams

被引：0
作者：
Malinauskas K.K. [1 ]
机构：
[1] Moscow State Institute of Electronic Technology (Technical University), Moscow
来源：
Journal of Mathematical Sciences | 2008年 / 154卷 / 2期
关键词：
Planar Graph; Voronoi Diagram; Outer Face; Dynamic Algorithm; Simple Closed Curve;
D O I：
10.1007/s10958-008-9160-x
中图分类号：
学科分类号：
摘要：
The abstract Voronoi diagram (AVD) introduced by R. Klein is a generalization of various concrete Voronoi diagrams-data structures actively used in the last decades for solving theoretical and practical geometric problems. This paper presents a fully dynamic algorithm for AVD construction based on Klein's incremental approach. It needs O(n) worst-case time for a new site insertion in an AVD with n sites. For the first time a possibility of effective site deletion without full reconstruction of AVD is proved. The proposed method for site deletion requires O(mn) expected time, where m is the number of invisible sites, and O(n) if invisible sites are not allowed. The dynamic algorithm consumes O(n) memory at any moment. © 2008 Springer Science+Business Media, Inc.
引用
收藏
页码：214 / 222
页数：8
相关论文
共 8 条
  • [1] Aurenhammer F., Voronoi diagrams: A survey of a fundamental geometric data structure, ACM Comput. Surveys, 23, pp. 345-405, (1991)
  • [2] Guibas L., Stofli J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, pp. 74-123, (1985)
  • [3] Kelley J.L., General Topology, (1975)
  • [4] Klein R., Abstract Voronoi diagrams and their applications, Lect. Notes Comput. Sci., 333, pp. 148-157, (1988)
  • [5] Klein R., Concrete and Abstract Voronoi Diagrams, Lect. Notes Comput. Sci., 400, (1989)
  • [6] Klein R., Mehlhorn K., Meiser S., Randomized incremental construction of abstract Voronoi diagrams, Comput. Geom., 3, pp. 157-184, (1993)
  • [7] Malinauskas K.K., Marchenko A.M., Voronoi diagrams based routing quality estimate for the placement task, IEEE AIS'03 and CAD-2003, pp. 70-74, (2003)
  • [8] Papadopoulou E., Lee D.T., The L <sub>∞</sub> Voronoi diagram of segments and VVLSI applications, Internat. J. Comput. Geom. Appl., 11, pp. 503-528, (2001)
1