Dynamic Voronoi diagram of complex sites

The Voronoi diagram (VD) is a fundamental geometric structure in many applications. There are fast and simple algorithms to construct the VD of static point sets. For complex sites (i.e., other than points) the algorithms are more sophisticated, and a few efficient solutions exist. However, updating...

Full description

Saved in:
Bibliographic Details
Published in:The Visual computer 2011-06, Vol.27 (6-8), p.463-472
Main Authors: Pinto, Francisco de Moura, Freitas, Carla Maria Dal Sasso
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computer Graphics
Computer Science
Image Processing and Computer Vision
Original Article
Voronoi graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Voronoi diagram (VD) is a fundamental geometric structure in many applications. There are fast and simple algorithms to construct the VD of static point sets. For complex sites (i.e., other than points) the algorithms are more sophisticated, and a few efficient solutions exist. However, updating the VD of dynamic sites is still challenging, and efficient solutions exist only for points. We propose an algorithm for constructing and updating the VD of large dynamic sets of complex sites. Although existing incremental algorithms allow fast insertion of complex sites, this work presents the first efficient implementation of the removal operation.
ISSN:0178-2789
1432-2315
DOI:10.1007/s00371-011-0581-z