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

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 (see Gold and al.

Año de publicación:

1997

Keywords:

Fuente:

google