An iterative algorithm for the determination of Voronoi vertices in polygonal and non-polygonal domains

François Anton, Christopher Gold

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We propose a new iterative algorithm for the computation of the vertices of a Voronoi diagram for a set of geometric objects of the euclidean plane. Each one of these vertices is the centre of the circle “touching” a triple of objects (passing through points or tangent to any other geometric object). The algorithm starts with an initial triple of points pertaining to each one of the three objects. It computes its circumcentre and the closest point (called foot) of each object from the circumcentre. These three feet form the starting triple for the next iteration. We geometrically demonstrate a necessary and sufficient condition for the general case. This iterative algorithm is used as a new method for constructing a dynamic Voronoi diagram for a set of points and straight line segments.
Original languageEnglish
Title of host publicationProceedings of the 9th Canadian Conference on Computational Geometry
Publication date1997
Pages257-262
Publication statusPublished - 1997
Externally publishedYes
Event9th Canadian Conference on Computational Geometry - Kingston, Canada
Duration: 11 Aug 199714 Aug 1997
Conference number: 9
http://www.cccg.ca/proceedings/1997/

Conference

Conference9th Canadian Conference on Computational Geometry
Number9
Country/TerritoryCanada
CityKingston
Period11/08/199714/08/1997
Internet address

Fingerprint

Dive into the research topics of 'An iterative algorithm for the determination of Voronoi vertices in polygonal and non-polygonal domains'. Together they form a unique fingerprint.

Cite this