Close Search Advanced
Journals
Resources
About Us
Open Access

2D Centroidal Voronoi Tessellations with Constraints

2D Centroidal Voronoi Tessellations with Constraints
Preview
Add to basket

Year:    2010

Numerical Mathematics: Theory, Methods and Applications, Vol. 3 (2010), Iss. 2 : pp. 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.

You do not have full access to this article.

Already a Subscriber? Sign in as an individual or via your institution

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/nmtma.2010.32s.6

Numerical Mathematics: Theory, Methods and Applications, Vol. 3 (2010), Iss. 2 : pp. 212–222

Published online:    2010-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    11

Keywords:    Centroidal Voronoi tessellation bounded Voronoi diagram constrained Delaunay triangulation

  1. Level Set Restricted Voronoi Tessellation for Large scale Spatial Statistical Analysis

    Neuroth, Tyson | Rieth, Martin | Aditya, Konduri | Lee, Myoungkyu | Chen, Jacqueline H | Ma, Kwan-Liu

    IEEE Transactions on Visualization and Computer Graphics, Vol. (2022), Iss. P.1

    https://doi.org/10.1109/TVCG.2022.3209473 [Citations: 1]

  2. Hybrid Voronoi Mesh Generation: Algorithms and Unsolved Problems

    Garanzha, V. A. | Kudryavtseva, L. N. | Tsvetkova, V. O.

    Computational Mathematics and Mathematical Physics, Vol. 59 (2019), Iss. 12 P.1945

    https://doi.org/10.1134/S0965542519120078 [Citations: 4]

  3. A Geometry-Aware Hidden Markov Model for Indoor Positioning

    Rudic, Branislav | Pichler-Scheder, Markus | Schmidt, Richard | Helmel, Christian | Efrosinin, Dmitry | Kastl, Christian | Auer, Wolfgang

    2020 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM), (2020), P.547

    https://doi.org/10.1109/AIM43001.2020.9159042 [Citations: 1]

  4. Q-MAT+: An error-controllable and feature-sensitive simplification algorithm for medial axis transform

    Pan, Yiling | Wang, Bin | Guo, Xiaohu | Zeng, Hua | Ma, Yuexin | Wang, Wenping

    Computer Aided Geometric Design, Vol. 71 (2019), Iss. P.16

    https://doi.org/10.1016/j.cagd.2019.04.007 [Citations: 14]

  5. Error-Bounded and Feature Preserving Surface Remeshing with Minimal Angle Improvement

    Hu, Kaimo | Yan, Dong-Ming | Bommes, David | Alliez, Pierre | Benes, Bedrich

    IEEE Transactions on Visualization and Computer Graphics, Vol. 23 (2017), Iss. 12 P.2560

    https://doi.org/10.1109/TVCG.2016.2632720 [Citations: 46]

  6. Computing 2D Periodic Centroidal Voronoi Tessellation

    Yan, Dong-Ming | Wang, Kai | Levy, Bruno | Alonso, Laurent

    2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering, (2011), P.177

    https://doi.org/10.1109/ISVD.2011.31 [Citations: 12]

  7. Mesh-based computation for solving bas-relief reconstruction from editable normal image

    Huang, Jin | Wang, Jun | Chen, Honghua | Guo, Xianglin | Wei, Mingqiang | Xie, Haoran | Qin, Jing

    Measurement Science and Technology, Vol. 30 (2019), Iss. 4 P.045402

    https://doi.org/10.1088/1361-6501/ab02d1 [Citations: 1]

  8. A method for generating moving, orthogonal, area preserving polygonal meshes

    Chartrand, Chris | Perot, J. Blair

    Journal of Computational Physics, Vol. 454 (2022), Iss. P.110940

    https://doi.org/10.1016/j.jcp.2022.110940 [Citations: 3]

  9. SurfaceVoronoi

    Xin, Shiqing | Wang, Pengfei | Xu, Rui | Yan, Dongming | Chen, Shuangmin | Wang, Wenping | Zhang, Caiming | Tu, Changhe

    ACM Transactions on Graphics, Vol. 41 (2022), Iss. 6 P.1

    https://doi.org/10.1145/3550454.3555453 [Citations: 6]

  10. Demonstrating environmental impacts on the sound structure of languages: challenges and solutions

    Maddieson, Ian | Benedict, Karl

    Frontiers in Psychology, Vol. 14 (2023), Iss.

    https://doi.org/10.3389/fpsyg.2023.1200463 [Citations: 3]

  11. Partly Centralized Partly Distributed Energy Efficient Sleep/Wake Scheduling in Wireless Sensor Networks for Applications Requiring Continuous Sensing

    Chauhan, Nilanshi | Chauhan, Siddhartha

    IETE Technical Review, Vol. 39 (2022), Iss. 4 P.940

    https://doi.org/10.1080/02564602.2021.1934906 [Citations: 1]

  12. TriMe++: Multi-threaded triangular meshing in two dimensions

    Lu, Jiayin | Rycroft, Chris H.

    Computer Physics Communications, Vol. (2024), Iss. P.109442

    https://doi.org/10.1016/j.cpc.2024.109442 [Citations: 0]

  13. Graph-Theory-Based Molecular Fragmentation for Efficient and Accurate Potential Surface Calculations in Multiple Dimensions

    Kumar, Anup | DeGregorio, Nicole | Iyengar, Srinivasan S.

    Journal of Chemical Theory and Computation, Vol. 17 (2021), Iss. 11 P.6671

    https://doi.org/10.1021/acs.jctc.1c00065 [Citations: 12]
  14. Operations Research Proceedings 2018

    Computation of Stable Honeycomb Structures for Additive Manufacturing

    Bähr, Martin | Radow, Georg | Breuß, Michael | Fügenschuh, Armin

    2019

    https://doi.org/10.1007/978-3-030-18500-8_45 [Citations: 0]

  15. Complex unstructured-grid groundwater modeling using centroidal Voronoi tessellation refinement and curve fitting

    Mohamed, Aya B.A. | Yang, Shuo | Chen, Ye-Hong | Tsai, Frank T.-C. | Dausman, Alyssa

    Journal of Hydrology, Vol. 637 (2024), Iss. P.131394

    https://doi.org/10.1016/j.jhydrol.2024.131394 [Citations: 0]

  16. Voronoi cell analysis: The shapes of particle systems

    Lazar, Emanuel A. | Lu, Jiayin | Rycroft, Chris H.

    American Journal of Physics, Vol. 90 (2022), Iss. 6 P.469

    https://doi.org/10.1119/5.0087591 [Citations: 27]
  17. Numerical Geometry, Grid Generation and Scientific Computing

    Structured Orthogonal Near-Boundary Voronoi Mesh Layers for Planar Domains

    Garanzha, Vladimir | Kudryavtseva, Liudmila | Tsvetkova, Valeriia

    2019

    https://doi.org/10.1007/978-3-030-23436-2_2 [Citations: 1]
  18. ICGG 2020 - Proceedings of the 19th International Conference on Geometry and Graphics

    Interactive Creation of Voronoi Diagrams for Origami Tessellation

    Yamamoto, Yohei | Mitani, Jun

    2021

    https://doi.org/10.1007/978-3-030-63403-2_20 [Citations: 0]