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 language | English |
---|---|
Title of host publication | Proceedings of the 9th Canadian Conference on Computational Geometry |
Publication date | 1997 |
Pages | 257-262 |
Publication status | Published - 1997 |
Externally published | Yes |
Event | 9th Canadian Conference on Computational Geometry - Kingston, Canada Duration: 11 Aug 1997 → 14 Aug 1997 Conference number: 9 http://www.cccg.ca/proceedings/1997/ |
Conference
Conference | 9th Canadian Conference on Computational Geometry |
---|---|
Number | 9 |
Country/Territory | Canada |
City | Kingston |
Period | 11/08/1997 → 14/08/1997 |
Internet address |