Skip to Main content Skip to Navigation
Book sections

Curved Voronoi diagrams

Jean-Daniel Boissonnat 1 Camille Wormser 1 Mariette Yvinec 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Voronoi diagrams are fundamental data structures that have been extensively studied in Computational Geometry. A Voronoi diagram can be defined as the minimization diagram of a finite set of continuous functions. Usually, each of those functions is interpreted as the distance function to an object. The as- sociated Voronoi diagram subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define many variants of Voronoi diagrams depending on the class of objects, the distance functions and the embedding space. Affine di- agrams, i.e. diagrams whose cells are convex polytopes, are well understood. Their properties can be deduced from the properties of polytopes and they can be constructed efficiently. The situation is very different for Voronoi dia- grams with curved regions. Curved Voronoi diagrams arise in various contexts where the objects are not punctual or the distance is not the Euclidean dis- tance. We survey the main results on curved Voronoi diagrams. We describe in some detail two general mechanisms to obtain effective algorithms for some classes of curved Voronoi diagrams. The first one consists in linearizing the diagram and applies, in particular, to diagrams whose bisectors are algebraic hypersurfaces. The second one is a randomized incremental paradigm that can construct affine and several planar non-affine diagrams. We finally introduce the concept of Medial Axis which generalizes the concept of Voronoi diagram to infinite sets. Interestingly, it is possible to efficiently construct a certified approximation of the medial axis of a bounded set from the Voronoi diagram of a sample of points on the boundary of the set.
Document type :
Book sections
Complete list of metadata
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Wednesday, June 2, 2010 - 8:44:23 AM
Last modification on : Saturday, January 27, 2018 - 1:31:32 AM
Long-term archiving on: : Friday, September 17, 2010 - 11:49:31 AM


Files produced by the author(s)


  • HAL Id : hal-00488446, version 1



Jean-Daniel Boissonnat, Camille Wormser, Mariette Yvinec. Curved Voronoi diagrams. Effective Computational Geometry for Curves and Surfaces, Springer, pp.67-116, 2007, Mathematics + Visualization. ⟨hal-00488446⟩



Record views


Files downloads