arrow
Volume 3, Issue 2
2D Centroidal Voronoi Tessellations with Constraints

Jane Tournois, Pierre Alliez & Olivier Devillers

Numer. Math. Theor. Meth. Appl., 3 (2010), pp. 212-222.

Published online: 2010-03

Export citation
  • Abstract

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.

  • Keywords

Centroidal Voronoi tessellation, bounded Voronoi diagram, constrained Delaunay triangulation

  • AMS Subject Headings

65M10, 78A48

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-3-212, author = {}, title = {2D Centroidal Voronoi Tessellations with Constraints}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2010}, volume = {3}, number = {2}, pages = {212--222}, abstract = {

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.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.2010.32s.6}, url = {http://global-sci.org/intro/article_detail/nmtma/5997.html} }
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 -

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.

Jane Tournois, Pierre Alliez & Olivier Devillers. (2020). 2D Centroidal Voronoi Tessellations with Constraints. Numerical Mathematics: Theory, Methods and Applications. 3 (2). 212-222. doi:10.4208/nmtma.2010.32s.6
Copy to clipboard
The citation has been copied to your clipboard