Document Open Access Logo

Generalizing CGAL Periodic Delaunay Triangulations

Authors Georg Osang , Mael Rouxel-Labbé, Monique Teillaud

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.75.pdf
  • Filesize: 0.69 MB
  • 17 pages

Document Identifiers

Author Details

Georg Osang
  • IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
Mael Rouxel-Labbé
  • GeometryFactory, Grasse, France
Monique Teillaud
  • Université de Lorraine, CNRS, Inria, LORIA, Nancy, France

Funding

  • Osang, Georg: This author is partially supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183.
  • Teillaud, Monique: This author is partially supported by the grants ANR-17-CE40-0033 of the French National Research Agency ANR (project SoS) and INTER/ANR 11554412/SoS of the Luxembourg National Research fund FNR ({https://members.loria.fr/Monique.Teillaud/collab/SoS/}).

Cite As Get BibTex

Georg Osang, Mael Rouxel-Labbé, and Monique Teillaud. Generalizing CGAL Periodic Delaunay Triangulations. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 75:1-75:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.75

Abstract

Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Delaunay triangulation
  • lattice
  • algorithm
  • software
  • experiments

Metrics

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

Supplementary Materials

References

  1. Erik Agrell, Thomas Eriksson, Alexander Vardy, and Kenneth Zeger. Closest point search in lattices. IEEE Trans. Inform. Theory, 48(8):2201-2214, 2002. URL: https://doi.org/10.1109/TIT.2002.800499.
  2. Miklós Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 10–19, New York, NY, USA, 1998. Association for Computing Machinery. URL: https://doi.org/10.1145/276698.276705.
  3. Adrian Bowyer. Computing Dirichlet tessellations. The computer journal, 24(2):162-166, 1981. Google Scholar
  4. Manuel Caroli. Triangulating Point Sets in Orbit Spaces. PhD thesis, Université Nice Sophia Antipolis, 2010. URL: https://tel.archives-ouvertes.fr/tel-00552215.
  5. Manuel Caroli, Aymeric Pellé, Mael Rouxel-Labbé, and Monique Teillaud. 3D periodic triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0.2 edition, 2020. URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic3Triangulation3.
  6. Manuel Caroli and Monique Teillaud. 3D periodic triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 3.5 edition, 2009. Google Scholar
  7. Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete & Computational Geometry, 55(4):827-853, 2016. URL: https://doi.org/10.1007/s00454-016-9782-6.
  8. J. H. Conway and N. J. A. Sloane. Low-dimensional lattices VI: Voronoi reduction of three-dimensional lattices. Proc. R. Soc. Lond. A, pages 55-68, 1992. Google Scholar
  9. B. Delaunay. Sur la sphère vide. À la mémoire de Georges Voronoï. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk, 7:793-800, 1934. URL: http://mi.mathnet.ru/eng/izv4937.
  10. Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping geometric triangulations on hyperbolic surfaces. In Proceedings of the Thirty-sixth International Symposium on Computational Geometry, 2020. To appear. Preliminary version: URL: https://hal.inria.fr/hal-02400219.
  11. Olivier Devillers and Monique Teillaud. Perturbations for Delaunay and weighted Delaunay 3D triangulations. Computational Geometry: Theory and Applications, 44:160-168, 2011. URL: https://doi.org/10.1016/j.comgeo.2010.09.010.
  12. Nikolai Dolbilin and Daniel Huson. Periodic Delone tilings. Periodica Mathematica Hungarica, 34:1-2:57-64, 1997. Google Scholar
  13. Peter Engel. Geometric crystallography: an axiomatic introduction to crystallography. Springer, Dordrecht, 1986. URL: https://doi.org/10.1007/978-94-009-4760-3.
  14. Clément Jamin, Sylvain Pion, and Monique Teillaud. 3D triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0.2 edition, 2020. URL: https://doc.cgal.org/latest/Manual/packages.html#PkgTriangulation3.
  15. Nico Kruithof. 2D periodic triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 4.4 edition, 2014. URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic2Triangulation2Summary.
  16. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput., 42(3):1364-1391, 2013. URL: https://doi.org/10.1137/100811970.
  17. The CGAL Project. URL: http://www.cgal.org.
  18. Chris Rycroft. Voro++: A three-dimensional Voronoi cell library in c++. Technical report, Lawrence Berkeley National Lab.(LBNL), Berkeley, CA (United States), 2009. URL: http://math.lbl.gov/voro++/.
  19. Naftali Sommer, Meir Feder, and Ofir Shalvi. Finding the closest lattice point by iterative slicing. SIAM J. Discrete Math., 23(2):715-731, 2009. URL: https://doi.org/10.1137/060676362.
  20. Peter van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, Mathematische Instituut, Uni. Amsterdam Report, April 1981. Google Scholar
  21. David F Watson. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. The computer journal, 24(2):167-172, 1981. Google Scholar
  22. Thomas F Willems, Chris H Rycroft, Michaeel Kazi, Juan C Meza, and Maciej Haranczyk. Algorithms and tools for high-throughput geometry-based analysis of crystalline porous materials. Microporous and Mesoporous Materials, 149(1):134-141, 2012. URL: http://zeoplusplus.org/.
  23. Mariette Yvinec. 2D triangulation. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0.2 edition, 2020. URL: https://doc.cgal.org/latest/Manual/packages.html#PkgTriangulation2.
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 About DROPS Imprint Privacy Contact