Delaunay Triangulations on Orientable Surfaces of Low Genus

Authors Mikhail Bogdanov, Monique Teillaud, Gert Vegter



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.20.pdf
  • Filesize: 1.14 MB
  • 17 pages

Document Identifiers

Author Details

Mikhail Bogdanov
Monique Teillaud
Gert Vegter

Cite AsGet BibTex

Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay Triangulations on Orientable Surfaces of Low Genus. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.20

Abstract

Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.
Keywords
  • covering spaces
  • hyperbolic surfaces
  • finitely presented groups
  • Fuchsian groups
  • systole

Metrics

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

References

  1. M. Artin. Algebra. Prentice-Hall, 2002. Google Scholar
  2. R. Aurich, E. B. Bogomolny, and F. Steiner. Periodic orbits on the regular hyperbolic octagon. Physica D: Nonlinear Phenomena, 48(1):91-101, 1991. URL: http://dx.doi.org/10.1016/0167-2789(91)90053-C.
  3. A. Bachelot-Motet. Wave computation on the hyperbolic double doughnut. Journal of Computational Mathematics, 28:1-17, 2010. URL: http://dx.doi.org/10.4208/jcm.1004.m3120.
  4. M. Berger. Geometry (vols. 1-2). Springer-Verlag, 1987. Google Scholar
  5. M. Bogdanov, O. Devillers, and M. Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry, 5:56-85, 2014. URL: http://jocg.org/index.php/jocg/article/view/141.
  6. M. Bogdanov and M. Teillaud. Delaunay triangulations and cycles on closed hyperbolic surfaces. Research Report 8434, INRIA, December 2013. URL: http://hal.inria.fr/hal-00921157.
  7. A. Bowyer. Computing Dirichlet tessellations. The Computer Journal, 24:162-166, 1981. Google Scholar
  8. P. Buser and P. Sarnak. On the period matrix of a Riemann surface of large genus. Inventiones mathematicae, 117:27-56, 1994. URL: http://dx.doi.org/10.1007/BF01232233.
  9. J. W. Cannon, W. J. Floyd, R. Kenyon, and W. R. Parry. Hyperbolic geometry. Flavors of geometry, 31:59-115, 1997. URL: http://www.math.uwo.ca/~shafikov/teaching/winter2010/4156/hyperbolic.pdf.
  10. M. Caroli. Triangulating Point Sets in Orbit Spaces. Phd thesis, Université de Nice-Sophia Antipolis, France, 2010. URL: http://tel.archives-ouvertes.fr/tel-00552215/.
  11. M. Caroli and M. Teillaud. 3D periodic triangulations. In CGAL Manual. CGAL Editorial Board, 3.5 edition, 2009. URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic3Triangulation3Summary.
  12. M. Caroli and M. Teillaud. Computing 3d periodic triangulations. In European Symposium on Algorithms, volume 5757 of LNCS, pages 59-70, 2009. To appear in [14]. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_6.
  13. M. Caroli and M. Teillaud. Delaunay triangulations of point sets in closed Euclidean d-manifolds. In Proc. 27th Symposium on Computational Geometry, pages 274-282, 2011. To appear in [14]. URL: http://dx.doi.org/10.1145/1998196.1998236.
  14. M. Caroli and M. Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete &Computational Geometry, To Appear. See also \citect-c3pt-09-short and [13]. Google Scholar
  15. P. Chossat, G. Faye, and O. Faugeras. Bifurcation of hyperbolic planforms. Journal of Nonlinear Science, 21:465-498, 2011. URL: http://dx.doi.org/10.1007/s00332-010-9089-3.
  16. É. Colin de Verdière, A. Hubard, and A. de Mesmay. Discrete systolic inequalities and decompositions of triangulated surfaces. In Proc. 30th Symposium on Computational Geometry, pages 335-344, 2014. To appear in Discrete &Computational Geometry. Google Scholar
  17. H. S. M. Coxeter and W. O. J. Moser. Generators and Relations for Discrete Groups. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1957. Google Scholar
  18. O. Devillers. Vertex removal in two-dimensional Delaunay triangulation: Speed-up by low degrees optimization. CGTA, 44:169-177, 2011. URL: http://dx.doi.org/10.1016/j.comgeo.2010.10.001.
  19. O. Devillers and M. Teillaud. Perturbations for Delaunay and weighted Delaunay 3D triangulations. CGTA, 44:160-168, 2011. URL: http://dx.doi.org/10.1016/j.comgeo.2010.09.010.
  20. N.P. Dolbilin and D.H. Huson. Periodic Delone tilings. Periodica Mathematica Hungarica, 34:1-2:57-64, 1997. Google Scholar
  21. Gap - groups, algorithms, programming. URL: http://www.gap-system.org.
  22. C. I. Grima and A. Márquez. Computational Geometry on Surfaces. Kluwer Academic Publishers, 2001. Google Scholar
  23. M. Gromov. Systoles and intersystolic inequalities. In Actes de la Table Ronde de Géométrie Différentielle (Luminy, 1992), volume 1 of Sémin. Congr., pages 291-362. Soc. Math. France, 1996. Google Scholar
  24. J. Hidding, R. vd Weygaert, G. Vegter, B.J.T. Jones, and M. Teillaud. Video: The sticky geometry of the cosmic web. In Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, pages 421-422, 2012. URL: http://www.computational-geometry.org/SoCG-videos/socg12video/.
  25. M.K. Hurdal and K. Stephenson. Cortical cartography using the discrete conformal approach of circle packings. Neuroimage, 23:119-128, 2004. Google Scholar
  26. S. Katok. Fuchsian Groups. Chicago Lectures in Mathematics. Uni. Chicago Press, 1992. Google Scholar
  27. N. 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.
  28. M. Mazón and T. Recio. Voronoi diagrams on orbifolds. Computational Geometry: Theory and Applications, 8:219-230, 1997. URL: http://dx.doi.org/10.1016/S0925-7721(96)00017-X.
  29. M. Naatanen. On the stability of identification patterns for Dirichlet regions. Annales Academiæ Scientiarum Fennicæ, Series A.I. Mathematica, 10:411-417, 1985. Google Scholar
  30. J. Ratcliffe. Foundations of Hyperbolic Manifolds. Graduate Texts in Mathematics. Springer, 2006. Google Scholar
  31. G. Ron, M. Jin, and X. Guo. Hyperbolic centroidal Voronoi tessellation. In Proc. ACM Symp. on Solid and Physical Modeling, pages 117-126, 2010. URL: http://dx.doi.org/10.1145/1839778.1839795.
  32. F. Sausset, G. Tarjus, and P. Viot. Tuning the fragility of a glassforming liquid by curving space. Physical Review Letters, 101:155701(1)-155701(4), 2008. URL: http://dx.doi.org/10.1103/PhysRevLett.101.155701.
  33. B. Schuetrumpf, M. A. Klatt, K. Iida, G. E. Schröder-Turk, J. A. Maruhn, K. Mecke, and P.-G. Reinhard. Appearance of the single gyroid network phase in “nuclear pasta” matter. Physical Review C, 91(025801), 2015. URL: http://dx.doi.org/10.1103/PhysRevC.91.025801.
  34. C.C. Sims. Computation with Finitely Presented Groups. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1994. Google Scholar
  35. T. Sousbie. The persistent cosmic web and its filament structure I. Monthly Notices of the Royal Astronomical Soc., 414:350–383, 2011. URL: http://dx.doi.org/10.1111/j.1365-2966.2011.18394.x.
  36. T. Sousbie, C. Pichon, and H. Kawahara. The persistent cosmic web and its filament structure II. Monthly Notices of the Royal Astronomical Society, 414:384–403, 2011. URL: http://dx.doi.org/10.1111/j.1365-2966.2011.18395.x.
  37. J. Stillwell. Geometry of Surfaces. Springer-Verlag, New York, 1992. Google Scholar
  38. W. P. Thurston. Three dimensional manifolds, Kleinian groups, and hyperbolic geometry. Bull. Amer. Math. Soc., 6(3):357-381, 1982. URL: http://www.ams.org/mathscinet-getitem?mr=648524.
  39. W. P. Thurston. Three Dimensional Geometry and Topology, vol. I. Princeton University Press, Princeton, New Jersey, 1997. Google Scholar
  40. R. vd Weygaert, G. Vegter, H. Edelsbrunner, B.J.T. Jones, P. Pranav, C. Park, W. A. Hellwing, B. Eldering, N. Kruithof, E.G.P. Bos, J. Hidding, J. Feldbrugge, E. ten Have, M. v Engelen, M. Caroli, and M. Teillaud. Alpha, Betti and the megaparsec universe: on the homology and topology of the cosmic web. In Trans. on Comp. Science XIV, volume 6970 of LNCS, pages 60-101. Springer-Verlag, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25249-5_3.
  41. P M. H. Wilson. Curved Spaces. Cambridge University Press, Cambridge, 2008. 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