On the hyperbolicity of Delaunay triangulations

Walter Carballosa; José M. Rodríguez; José M. Sigarreta; Walter Carballosa; José M. Rodríguez; José M. Sigarreta

doi:10.3934/math.20231474

AIMS Mathematics

2023, Volume 8, Issue 12: 28780-28790. doi: 10.3934/math.20231474

Previous Article Next Article

Research article Special Issues

On the hyperbolicity of Delaunay triangulations

1.
Department of Mathematics and Statistics, Florida International University, 11200 SW 8th Street, Miami, FL 33199, USA
2.
Departamento de Matemáticas, Universidad Carlos Ⅲ de Madrid, Avenida de la Universidad 30, 28911 Leganés, Madrid, Spain
3.
Facultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame No.54 Col. Garita, 39650 Acalpulco Gro., Mexico

Received: 29 May 2023 Revised: 11 October 2023 Accepted: 17 October 2023 Published: 23 October 2023
MSC : 05C10, 05C63, 05C99

If $ X $ is a geodesic metric space and $ x_1, x_2, x_3\in X $, a geodesic triangle $ T = \{x_1, x_2, x_3\} $ is the union of the three geodesics $ [x_1 x_2] $, $ [x_2 x_3] $ and $ [x_3 x_1] $ in $ X $. The space $ X $ is hyperbolic if there exists a constant $ \delta \ge 0 $ such that any side of any geodesic triangle in $ X $ is contained in the $ \delta $-neighborhood of the union of the two other sides. In this paper, we study the hyperbolicity of an important kind of Euclidean graphs called Delaunay triangulations. Furthermore, we characterize the Delaunay triangulations contained in the Euclidean plane that are hyperbolic.
- Delaunay triangulation,
- Voronoi graph,
- hyperbolic graphs,
- tessellation graphs
Citation: Walter Carballosa, José M. Rodríguez, José M. Sigarreta. On the hyperbolicity of Delaunay triangulations[J]. AIMS Mathematics, 2023, 8(12): 28780-28790. doi: 10.3934/math.20231474

Related Papers:

Abstract

If $ X $ is a geodesic metric space and $ x_1, x_2, x_3\in X $, a geodesic triangle $ T = \{x_1, x_2, x_3\} $ is the union of the three geodesics $ [x_1 x_2] $, $ [x_2 x_3] $ and $ [x_3 x_1] $ in $ X $. The space $ X $ is hyperbolic if there exists a constant $ \delta \ge 0 $ such that any side of any geodesic triangle in $ X $ is contained in the $ \delta $-neighborhood of the union of the two other sides. In this paper, we study the hyperbolicity of an important kind of Euclidean graphs called Delaunay triangulations. Furthermore, we characterize the Delaunay triangulations contained in the Euclidean plane that are hyperbolic.

References

[1]	J. Alonso, T. Brady, D. Cooper, T. Delzant, V. Ferlini, M. Lustig, et al., Notes on word hyperbolic groups, in: E. Ghys, A. Haefliger, A. Verjovsky (Eds.), Group Theory from a Geometrical Viewpoint, World Scientific, Singapore, 1992.
[2]	E. Ghys, P. Harpe, Sur les Groupes Hyperboliques d'après Mikhael Gromov, Progress in Mathematics 83, Birkhäuser Boston Inc., Boston, MA, 1990. https://doi.org/10.1007/978-1-4684-9167-8
[3]	M. Gromov, Hyperbolic groups, in "Essays in group theory", Edited by S. M. Gersten, M. S. R. I. Publ., Springer, New York, NY, 1987, 75–263. https://doi.org/10.1007/978-1-4613-9586-7-3
[4]	K. Oshika, Discrete groups, AMS Bookstore, 2002.
[5]	R. Charney, Artin groups of finite type are biautomatic, Math. Ann., 292 (1992), 671–683. https://doi.org/10.1007/BF01444642 doi: 10.1007/BF01444642
[6]	E. Tourís, Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl., 380 (2011), 865–881. https://doi.org/10.1016/j.jmaa.2011.02.067 doi: 10.1016/j.jmaa.2011.02.067
[7]	R. Krauthgamer, J. R. Lee, Algorithms on negatively curved spaces, FOCS 2006.
[8]	Y. Shang, Lack of Gromov-hyperbolicity in colored random networks, Pan-American Math. J., 21 (2011), 27–36.
[9]	Y. Shang, Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math., 10 (2012), 1152–1158. https://doi.org/10.2478/s11533-012-0032-8 doi: 10.2478/s11533-012-0032-8
[10]	Y. Shang, Non-hyperbolicity of random graphs with given expected degrees, Stoch. Models, 29 (2013), 451–462. https://doi.org/10.1080/15326349.2013.838510 doi: 10.1080/15326349.2013.838510
[11]	K. Verbeek, S. Suri, Metric embeddings, hyperbolic space and social networks, Discret. Math., 59 (2016), 1–12. https://doi.org/10.1016/j.comgeo.2016.08.003 doi: 10.1016/j.comgeo.2016.08.003
[12]	M. Abu-Ata, F. F. Dragan, Metric tree-like structures in real-life networks: An empirical study, Networks, 67 (2016), 49–68. https://doi.org/10.1002/net.21631 doi: 10.1002/net.21631
[13]	Y. Shavitt, T. Tankel, On internet embedding in hyperbolic spaces for overlay construction and distance estimation, INFOCOM 2004.
[14]	D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, M. Boguña, Hyperbolic geometry of complex networks, Phys. Rev. E, 82 (2010), 036106. https://doi.org/10.1103/physreve.82.036106 doi: 10.1103/physreve.82.036106
[15]	E. Jonckheere, Contrôle du traffic sur les réseaux à géométrie hyperbolique–Vers une théorie géométrique de la sécurité l'acheminement de l'information, J. Europ. Syst. Autom., 8 (2002), 45–60.
[16]	E. Jonckheere, P. Lohsoonthorn, Geometry of network security, Amer. Control Conf., ACC (2004), 111–151.
[17]	O. Narayan, I. Saniee, Large-scale curvature of networks, Phys. Rev. E, 84 (2011), 066108. https://doi.org/10.1103/physreve.84.066108 doi: 10.1103/physreve.84.066108
[18]	F. Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Comput. Surv., 3 (1991), 345–405. https://doi.org/10.1145/116873.116880 doi: 10.1145/116873.116880
[19]	F. Aurenhammer, R. Klein, Voronoi diagrams, In Handbook of computational geometry, (J. Sack and G. Urrutia, Eds.), North-Holland, Amsterdam, 2000,201–290.
[20]	G. Voronoi, Nouvelles applications des parametres continus à la theorie des formes quadratiques, J. Reine. Angew. Math., 134 (1908), 198–287. https://doi.org/10.1515/crll.1908.134.198 doi: 10.1515/crll.1908.134.198
[21]	R. Sedgewick, J. Vitter, Shortest paths in Euclidean graphs, Algorithmica, 1 (1986), 31–48. https://doi.org/10.1109/sfcs.1984.715943 doi: 10.1109/sfcs.1984.715943
[22]	P. Chew, There is a planar graph almost as good as the complete graph, In Proceedings of the Second Symposium on Computational Geometry, Yorktown Heights, NY, 1986, pp. 169–177. https://doi.org/10.1145/10515.10534
[23]	F. P. Preparata, M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. https://doi.org/10.1007/978-1-4612-1098-6
[24]	W. Carballosa, Gromov hyperbolicity and convex tessellation graph, Acta Math. Hungar., 151 (2017), 24–34. https://doi.org/10.1007/s10474-016-0677-z doi: 10.1007/s10474-016-0677-z
[25]	B. H. Bowditch, Notes on Gromov's hyperbolicity criterion for path-metric spaces in Group theory from a geometrical viewpoint, ed. E. Ghys, A. Haefliger and A. Verjovsky; World Scientific, River Edge, NJ, 1991, 64–167.
[26]	J. C. Hernández, G. Reyna, O. Rosario, Results on hyperbolicity in graphs: a survey, Discret. Math. Lett., 4 (2011), 60–72.
[27]	Á. Martínez, Quasi-isometries between visual hyperbolic spaces, Manus. Math., 137 (2012), 195–213 https://doi.org/10.1007/s00229-011-0463-8 doi: 10.1007/s00229-011-0463-8
[28]	S. Bermudo, J. M. Rodríguez, J. M. Sigarreta, J. M. Vilaire, Gromov hyperbolic graphs, Discret. Math., 313 (2013), 1575–1585. https://doi.org/10.1016/j.disc.2013.04.009 doi: 10.1016/j.disc.2013.04.009
[29]	A. Cantón, A. Granados, D. Pestana, J. M. Rodríguez, Gromov hyperbolicity of periodic graphs, Acta. Math. Sin. English Ser., 30 (2014), 79–90. https://doi.org/10.1007/s10114-013-2370-2 doi: 10.1007/s10114-013-2370-2
[30]	J. M. Rodríguez, J. M. Sigarreta, Y. Torres-Nuñez, Computing the hyperbolicity constant of a cubic graph, Int. J. Comput Math., 91 (2014), 1897–1910.
[31]	Y. Wu, C. Zhang, Chordality and hyperbolicity of a graph, Electr. J. Comb., 18 (2011), 43. https://doi.org/10.37236/530 doi: 10.37236/530
[32]	D. Delaunay, Sur la sphère vide: A la mémoire de Georges Voronoï, Bull. Acad. Sci. URSS, Classe Sci. Math. Natur., 6 (1934), 793–800.
[33]	J. M. Keil, C. A. Gutwin, Classes of graphs which approximate the Complete Euclidean Graph, Discr. Comput. Geom., 7 (1992), 13–28. https://doi.org/10.1007/BF02187821 doi: 10.1007/BF02187821

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)