TY - JOUR
T1 - 2D Centroidal Voronoi Tessellations with Constraints
JO - Numerical Mathematics: Theory, Methods and Applications
VL - 2
SP - 212
EP - 222
PY - 2010
DA - 2010/03
SN - 3
DO - http://doi.org/10.4208/nmtma.2010.32s.6
UR - https://global-sci.org/intro/article_detail/nmtma/5997.html
KW - Centroidal Voronoi tessellation, bounded Voronoi diagram, constrained Delaunay triangulation
AB - <p style="text-align: justify;">We 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 vertices are hidden by the constraint. The resulting construction is amenable to
Lloyd relaxation so as to obtain a centroidal tessellation with constraints.</p>