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.
|Title of host publication||Proceedings of the 9th Canadian Conference on Computational Geometry|
|Publication status||Published - 1997|
|Event||9th Canadian Conference on Computational Geometry - Kingston, Canada|
Duration: 11 Aug 1997 → 14 Aug 1997
Conference number: 9
|Conference||9th Canadian Conference on Computational Geometry|
|Period||11/08/1997 → 14/08/1997|