Document Open Access Logo

Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams

Authors Jean-Daniel Boissonnat, Mael Rouxel-Labbé, Mathijs Wintraecken

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.19.pdf
  • Filesize: 1.69 MB
  • 16 pages

Document Identifiers

Author Details

Jean-Daniel Boissonnat
Mael Rouxel-Labbé
Mathijs Wintraecken

Cite AsGet BibTex

Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs Wintraecken. Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.19

Abstract

The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in R^2 and on surfaces embedded in R^3 as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points P in a domain Omega equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of P to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in Omega under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.
Keywords
  • Riemannian Geometry
  • Voronoi diagram
  • Delaunay triangulation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. F. Aurenhammer and R. Klein. Voronoi diagrams. In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry, pages 201-290. Elsevier Science Publishing, 2000. Google Scholar
  2. J.-D. Boissonnat, R. Dyer, and A. Ghosh. Delaunay triangulation of manifolds. Foundations of Computational Mathematics, pages 1-33, 2017. Google Scholar
  3. J.-D. Boissonnat, R. Dyer, A. Ghosh, and S. Y. Oudot. Only distances are required to reconstruct submanifolds. Comp. Geom. Theory and Appl., 2016. To appear. Google Scholar
  4. J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken. Anisotropic triangulations via discrete Riemannian Voronoi diagrams, 2017. URL: https://arxiv.org/abs/1703.06487.
  5. M. Campen, M. Heistermann, and L. Kobbelt. Practical anisotropic geodesy. In Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing, SGP'13, pages 63-71. Eurographics Association, 2013. Google Scholar
  6. G. D. Cañas and S. J. Gortler. Orphan-free anisotropic Voronoi diagrams. Discrete and Computational Geometry, 46(3), 2011. Google Scholar
  7. G. D. Cañas and S. J. Gortler. Duals of orphan-free anisotropic Voronoi diagrams are embedded meshes. In SoCG, pages 219-228. ACM, 2012. Google Scholar
  8. T. Cao, H. Edelsbrunner, and T. Tan. Proof of correctness of the digital Delaunay triangulation algorithm. Comp. Geo.: Theory and Applications, 48, 2015. Google Scholar
  9. S.-W. Cheng, T. K. Dey, E. A. Ramos, and R. Wenger. Anisotropic surface meshing. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 202-211. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  10. E. F. D'Azevedo and R. B. Simpson. On optimal interpolation triangle incidences. SIAM J. Sci. Statist. Comput., 10(6):1063-1075, 1989. Google Scholar
  11. T. K. Dey, F. Fan, and Y. Wang. Graph induced complex on point data. Computational Geometry, 48(8):575-588, 2015. Google Scholar
  12. Q. Du and D. Wang. Anisotropic centroidal Voronoi tessellations and their applications. SIAM Journal on Scientific Computing, 26(3):737-761, 2005. Google Scholar
  13. R. Dyer, G. Vegter, and M. Wintraecken. Riemannian simplices and triangulations. Preprint: arXiv:1406.3740, 2014. Google Scholar
  14. R. Dyer, H. Zhang, and T. Möller. Surface sampling and the intrinsic Voronoi diagram. Computer Graphics Forum, 27(5):1393-1402, 2008. Google Scholar
  15. M. Garland and P. S. Heckbert. Surface simplification using quadric error metrics. In ACM SIGGRAPH, pages 209-216, 1997. Google Scholar
  16. H. Karcher. Riemannian center of mass and mollifier smoothing. Communications on Pure and Applied Mathematics, 30:509-541, 1977. Google Scholar
  17. F. Labelle and J. R. Shewchuk. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SCG'03: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pages 191-200. ACM, 2003. Google Scholar
  18. G. Leibon. Random Delaunay triangulations, the Thurston-Andreev theorem, and metric uniformization. PhD thesis, UCSD, 1999. Google Scholar
  19. J.-M. Mirebeau. Optimal meshes for finite elements of arbitrary order. Constructive approximation, 32(2):339-383, 2010. Google Scholar
  20. P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete &Comp. Geom., 39(1-3), 2008. Google Scholar
  21. G. Peyré, M. Péchaud, R. Keriven, and L. D. Cohen. Geodesic methods in computer vision and graphics. Found. Trends. Comput. Graph. Vis., 2010. Google Scholar
  22. C. Rourke and B. Sanderson. Introduction to piecewise-linear topology. Springer Science &Business Media, 2012. Google Scholar
  23. M. Rouxel-Labbé, M. Wintraecken, and J.-D. Boissonnat. Discretized Riemannian Delaunay triangulations. In Proc. of the 25th Intern. Mesh. Round. Elsevier, 2016. Google Scholar
  24. J. R. Shewchuk. What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures, Manuscript 2002. Google Scholar
  25. E. Sperner. Fifty years of further development of a combinatorial lemma. Numerical solution of highly nonlinear problems, pages 183-197, 1980. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact