Dynamic construction of abstract Voronoi diagrams
Fundamentalʹnaâ i prikladnaâ matematika, Tome 13 (2007) no. 2, pp. 133-146
Voir la notice de l'article provenant de la source Math-Net.Ru
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\df 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.
@article{FPM_2007_13_2_a4,
author = {K. K. Malinauskas},
title = {Dynamic construction of abstract {Voronoi} diagrams},
journal = {Fundamentalʹna\^a i prikladna\^a matematika},
pages = {133--146},
publisher = {mathdoc},
volume = {13},
number = {2},
year = {2007},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/FPM_2007_13_2_a4/}
}
K. K. Malinauskas. Dynamic construction of abstract Voronoi diagrams. Fundamentalʹnaâ i prikladnaâ matematika, Tome 13 (2007) no. 2, pp. 133-146. http://geodesic.mathdoc.fr/item/FPM_2007_13_2_a4/