Paper Info
Title
Interactive Analysis Using Voronoi Diagrams: Algorithms to Support Dynamic Update from a Generic Triangle-based Data Structure
Abstract
This paper describes a series of dynamic update methods th at can be applied to a family of Voronoi diagram types, so that changes can be updated incrementa lly, without the usual recourse to complete reconstruction of their underlying data structure. Mor e efficient incremental update methods are described for the ordinary Voronoi diagram, the farthest-point Voronoi diagram, the order-k Voronoi diagram, the ordered order- k Voronoi diagram and the kth nearest-point Voronoi diagram. A discussion is also given of one case where increme ntal update is not practical, that of the multiplicatively weighted Voronoi diagram. Update methods rely on a previously reported generic triangle-based data structure (Gahegan & Lee, 2000) f rom which local topology can be reconstructed following changes to the underlying pointset. An a pplication, which implements these ideas, is available for download via the Internet as proof of concept. Results show that the algorithmic complexity of dynamic update methods vary considerably according to the Voronoi type, but offer in all cases (except the multiplicativel y weighted Voronoi diagram) a substantial increase in performance, enabling Voronoi methods to addre ss larger pointsets and more complex modelling problems without suffering from efficiency problems.
Year
DOI
Venue
2002
10.1111/1467-9671.00099
T. GIS
Keywords
DocType
Volume
voronoi diagrams,computational efficiency.,dynamic update,interactive spatial analy sis,proof of concept,data structure,voronoi diagram
Journal
6
Issue
Citations 
PageRank 
2
4
0.50
References 
Authors
12
2
Name
Order
Citations
PageRank
Ickjai Lee137244.05
Mark Gahegan257155.38