×

Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions. (English) Zbl 1307.05056

Summary: Motivated by low energy consumption in geographic routing in wireless networks, there has been recent interest in determining bounds on the length of edges in the Delaunay graph of randomly distributed points. Asymptotic results are known for random networks in planar domains. In this paper, we obtain upper and lower bounds that hold with parametric probability in any dimension, for points distributed uniformly at random in domains with and without boundary. The results obtained are asymptotically tight for all relevant values of such probability and constant number of dimensions, and show that the overhead produced by boundary nodes in the plane holds also for higher dimensions. To our knowledge, this is the first comprehensive study on the lengths of long edges in Delaunay graphs.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arkin, E. M.; Fernández Anta, A.; Mitchell, J. S.B.; Mosteiro, M., The length of the longest edge in multi-dimensional Delaunay graphs (extended abstract), (Proceedings of the 20th Annual Fall Workshop on Computational Geometry (2010))
[2] Arkin, E. M.; Fernández Anta, A.; Mitchell, J. S.B.; Mosteiro, M., Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions, (Proceedings of the 23rd Canadian Conference on Computational Geometry (2011)), 163-168
[3] de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational Geometry: Algorithms and Applications (2000), Springer-Verlag · Zbl 0939.68134
[4] Penrose, M., Random Geometric Graphs (2003), Oxford University Press · Zbl 1029.60007
[5] Bose, P.; Morin, P., Online routing in triangulations, (Proc. of the 10th International Symposium on Algorithms and Computation (1999), Springer-Verlag), 113 · Zbl 0964.68138
[6] Kozma, G.; Lotker, Z.; Sharir, M.; Stupp, G., Geometrically aware communication in random wireless networks, (Proc. 23rd Ann. ACM Symp. on Principles of Distributed Computing (2004)), 310-319 · Zbl 1321.90033
[7] Kranakis, E.; Singh, H.; Urrutia, J., Compass routing on geometric networks, (Proc. of the 11th Canadian Conference on Computational Geometry (1999))
[8] Lebhar, E.; Lotker, Z., Unit disk graph and physical interference model: putting pieces together, (Proc. of the 23rd International Symposium on Parallel & Distributed Processing (2009), IEEE), 1-8
[9] Bern, M.; Eppstein, D.; Yao, F., The expected extremes in a Delaunay triangulation, Int. J. Comput. Geom. Appl., 1, 1, 79-91 (1991) · Zbl 0724.68084
[10] Wan, P.; Yi, C., On the longest edge of Gabriel graphs in wireless ad hoc networks, IEEE Trans. Parallel Distrib. Syst., 111-125 (2007)
[11] Wan, P.; Wang, L.; Yao, F.; Yi, C., On the longest RNG edge of wireless ad hoc networks, (Proc. of the 28th International Conference on Distributed Computing Systems (2008), IEEE), 329-336
[12] Yi, C.; Wan, P.; Wang, L.; Su, C., Sharp thresholds for relative neighborhood graphs in wireless ad hoc networks, IEEE Trans. Wirel. Commun., 9, 2, 614-623 (2010)
[13] Devroye, L.; Gudmundsson, J.; Morin, P., On the expected maximum degree of Gabriel and Yao graphs (May 2009) · Zbl 1196.60019
[14] Aldous, D.; Shun, J., Connected spatial networks over random points and a route-length statistic, Stat. Sci., 25, 3, 275-288 (2010) · Zbl 1329.60009
[15] Bose, P.; Carmi, P.; Smid, M. H.M.; Xu, D., Communication-efficient construction of the plane localized Delaunay graph, (Proc. of the 9th Latin American Theoretical Informatics Symposium (2010)), 282-293 · Zbl 1283.05255
[16] Avin, C., Fast and efficient restricted Delaunay triangulation in random geometric graphs, Internet Math., 5, 3, 195-210 (2008) · Zbl 1195.68103
[17] Araújo, F.; Rodrigues, L., Single-step creation of localized Delaunay triangulations, Wirel. Netw., 15, 7, 845-858 (2009)
[18] Lemaire, C.; Moreau, J., A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Comput. Geom., 17, 1-2, 69-96 (2000) · Zbl 0971.68182
[19] Mitrinović, D. S., Elementary Inequalities (1964), P. Noordhoff Ltd.: P. Noordhoff Ltd. Groningen · Zbl 0121.05302
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.