A hierarchical raster method for computing voronoi diagrams based on quadtrees

Renliang Zhao, Zhilin Li, Jun Chen, C. M. Gold, Yong Zhang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

6 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationComputational Science, ICCS 2002 - International Conference, Proceedings
Number of pages10
EditionPART 3
Publication statusPublished - 1 Dec 2002
EventInternational Conference on Computational Science, ICCS 2002 - Amsterdam, Netherlands
Duration: 21 Apr 200224 Apr 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 3
Volume2331 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Computational Science, ICCS 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A hierarchical raster method for computing voronoi diagrams based on quadtrees'. Together they form a unique fingerprint.

Cite this