Paper Info
Title
A Hierarchical Raster Method for Computing Voronoi Diagrams Based on Quadtrees
Abstract
Voronoi diagram is a basic data structure in geometry. It has been increasingly attracting the investigation into diverse applications since it was introduced into GIS field. Most current methods for computing Voronoi diagrams are implemented in vector mode. However, the vector-based methods are good only for points and difficult for complex objects. At the same time, most current raster methods are implemented only in a uniformed-grid raster mode. There is a lack of hierarchical method implemented in a hierarchical space such as quadtrees. In this paper such a hierarchical method is described for computing generalized Voronoi diagrams by means of hierarchical distance transform and hierarchical morphological operators based on the quadtree structure. Three different solutions are described and illustrated with experiments for different applications. Furthermore, the errors caused by this method are analyzed and are reduced by constructing the dynamical hierarchical distance structure elements.
Year
DOI
Venue
2002
10.1007/3-540-47789-6_106
International Conference on Computational Science (3)
Keywords
Field
DocType
dynamical hierarchical distance structure,hierarchical distance,hierarchical method,basic data structure,generalized voronoi diagram,current raster method,hierarchical space,computing voronoi,current method,voronoi diagram,hierarchical raster method,hierarchical morphological operator,data structure,distance transform
Data structure,Raster graphics,Centroidal Voronoi tessellation,Mathematical morphology,Computer science,Computational geometry,Algorithm,Distance transform,Voronoi diagram,Quadtree
Conference
Volume
ISSN
ISBN
2331
0302-9743
3-540-43594-8
Citations 
PageRank 
References 
1
0.38
15
Authors
5
Name
Order
Citations
PageRank
Renliang Zhao1315.85
Zhilin Li243362.27
Jun Chen320721.33
Christopher M. Gold428935.07
Yong Zhang510.38