Open Access2D Centroidal Voronoi Tessellations with Constraints
Author(s) -
Jane Tournois
Publication year - 2010
Publication title -
numerical mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.64
H-Index - 23
eISSN - 2079-7338
pISSN - 1004-8979
DOI - 10.4208/nmtma.2010.32s.6
Subject(s) - centroidal voronoi tessellation , voronoi diagram , delaunay triangulation , bowyer–watson algorithm , weighted voronoi diagram , pitteway triangulation , constrained delaunay triangulation , mathematics , bounded function , power diagram , constraint (computer aided design) , combinatorics , computer science , geometry , mathematical analysis
International audienceWe tackle the problem of constructing 2D centroidal Voronoi tessellations with constraints through an efficient and robust construction of bounded Voronoi diagrams, the pseudo-dual of the constrained Delaunay triangulation. We exploit the fact that the cells of the bounded Voronoi diagram can be obtained by clipping the ordinary ones against the constrained Delaunay edges. The clipping itself is efficiently computed by identifying for each constrained edge the (connected) set of triangles whose dual Voronoi vertex is hidden by the constraint. The resulting construction is amenable to Lloyd relaxation so as to obtain a centroidal tessellation with constraints