FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2007, VOLUME 13, NUMBER 2, PAGES 133-146

Dynamic construction of abstract Voronoi diagrams

K. K. Malinauskas

Abstract

View as HTML     View as gif image

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.

Location: http://mech.math.msu.su/~fpm/eng/k07/k072/k07205h.htm
Last modified: May 23, 2007