Bonnet, Gilles; Chenavier, Nicolas The maximal degree in a Poisson-Delaunay graph. (English) Zbl 1466.60100 Bernoulli 26, No. 2, 948-979 (2020). Summary: We investigate the maximal degree in a Poisson-Delaunay graph in \(\mathbb{R}^d\), \(d\geq 2\), over all nodes in the window \(\mathbf{W}_{\rho}:=\rho^{1/d}[0,1]^d\) as \(\rho\) goes to infinity. The exact order of this maximum is provided in any dimension. In the particular setting \(d=2\), we show that this quantity is concentrated on two consecutive integers with high probability. A weaker version of this result is discussed when \(d\geq 3\). Cited in 5 Documents MSC: 60G55 Point processes (e.g., Poisson, Cox, Hawkes processes) 60D05 Geometric probability and stochastic geometry 60G70 Extreme value theory; extremal stochastic processes Keywords:degree; Delaunay graph; extreme values; Poisson point process × Cite Format Result Cite Review PDF Full Text: DOI arXiv Euclid References: [1] Anderson, C.W. (1970). Extreme value theory for a class of discrete distributions with applications to some stochastic processes. J. Appl. Probab. 7 99-113. · Zbl 0192.54202 · doi:10.2307/3212152 [2] Aurenhammer, F., Klein, R. and Lee, D.-T. (2013). Voronoi Diagrams and Delaunay Triangulations. Hackensack, NJ: World Scientific Co. Pte. Ltd. · Zbl 1295.52001 [3] Avram, F. and Bertsimas, D. (1993). On central limit theorems in geometrical probability. Ann. Appl. Probab. 3 1033-1046. · Zbl 0784.60015 · doi:10.1214/aoap/1177005271 [4] Bern, M., Eppstein, D. and Yao, F. (1991). The expected extremes in a Delaunay triangulation. In Automata, Languages and Programming (Madrid, 1991). Lecture Notes in Computer Science 510 674-685. Berlin: Springer. · Zbl 0769.68116 [5] Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge Studies in Advanced Mathematics 73. Cambridge: Cambridge Univ. Press. [6] Bonnet, G. (2016). Poisson hyperplane tessellation: Asymptotic probabilities of the zero and typical cells. Ph.D. thesis, Univ. of Osnabrück. [7] Bonnet, G., Calka, P. and Reitzner, M. (2018). Cells with many facets in a Poisson hyperplane tessellation. Adv. Math. 324 203-240. · Zbl 1388.60041 · doi:10.1016/j.aim.2017.11.016 [8] Broutin, N., Devillers, O. and Hemsley, R. (2014). The maximum degree of a random Delaunay triangulation in a smooth convex. In AofA - 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. · Zbl 1331.68246 [9] Calka, P. (2003). An explicit expression for the distribution of the number of sides of the typical Poisson-Voronoi cell. Adv. in Appl. Probab. 35 863-870. · Zbl 1038.60008 · doi:10.1239/aap/1067436323 [10] Carr, R., Goh, W.M.Y. and Schmutz, E. (1994). The maximum degree in a random tree and related problems. Random Structures Algorithms 5 13-24. · Zbl 0797.60015 · doi:10.1002/rsa.3240050104 [11] Cazals, F. and Giesen, J. (2006). Delaunay triangulation based surface reconstruction. In Effective Computational Geometry for Curves and Surfaces 231-276. Springer. · Zbl 1116.65022 [12] Chenavier, N. (2014). A general study of extremes of stationary tessellations with examples. Stochastic Process. Appl. 124 2917-2953. · Zbl 1359.60023 · doi:10.1016/j.spa.2014.04.009 [13] Chenavier, N. and Devillers, O. (2018). Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity. Adv. in Appl. Probab. 50 35-56. · Zbl 1431.60012 [14] Chenavier, N. and Robert, C.Y. (2018). Cluster size distributions of extreme values for the Poisson-Voronoi tessellation. Ann. Appl. Probab. 28 3291-3323. · Zbl 1404.60024 · doi:10.1214/17-AAP1345 [15] Cheng, S.-W., Dey, T.K. and Shewchuk, J.R. (2012). Delaunay Mesh Generation. Chapman & Hall/CRC Computer and Information Science Series. Boca Raton, FL: CRC Press/CRC. [16] Drmota, M., Giménez, O., Noy, M., Panagiotou, K. and Steger, A. (2014). The maximum degree of random planar graphs. Proc. Lond. Math. Soc. (3) 109 892-920. · Zbl 1303.05176 · doi:10.1112/plms/pdu024 [17] Gao, Z. and Wormald, N.C. (2000). The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 201-230. · Zbl 0944.05057 · doi:10.1006/jcta.1999.3006 [18] Giménez, O., Mitsche, D. and Noy, M. (2016). Maximum degree in minor-closed classes of graphs. European J. Combin. 55 41-61. · Zbl 1333.05079 · doi:10.1016/j.ejc.2016.02.001 [19] Hilhorst, H.J. (2005). Asymptotic statistics of the \(n\)-sided planar Poisson-Voronoi cell. I. Exact results. J. Stat. Mech. Theory Exp. 9 P09005, 45. · Zbl 1456.60040 [20] Hilhorst, H.J. and Calka, P. (2008). Random line tessellations of the plane: Statistical properties of many-sided cells. J. Stat. Phys. 132 627-647. · Zbl 1160.60005 · doi:10.1007/s10955-008-9577-0 [21] Kimber, A.C. (1983). A note on Poisson maxima. Z. Wahrsch. Verw. Gebiete 63 551-552. · Zbl 0514.60035 · doi:10.1007/BF00533727 [22] Kuai, H., Alajaji, F. and Takahara, G. (2000). A lower bound on the probability of a finite union of events. Discrete Math. 215 147-158. · Zbl 0960.60017 · doi:10.1016/S0012-365X(99)00246-0 [23] Last, G. and Penrose, M. (2017). Lectures on the Poisson Process. Institute of Mathematical Statistics Textbooks 7. Cambridge: Cambridge Univ. Press. [24] McDiarmid, C. and Reed, B. (2008). On the maximum degree of a random planar graph. Combin. Probab. Comput. 17 591-601. · Zbl 1160.05018 · doi:10.1017/S0963548308009097 [25] McDiarmid, C., Steger, A. and Welsh, D.J.A. (2006). Random graphs from planar and other addable classes. In Topics in Discrete Mathematics. Algorithms Combin. 26 231-246. Berlin: Springer. · Zbl 1119.05099 [26] Okabe, A., Boots, B., Sugihara, K. and Chiu, S.N. (2000). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed. Wiley Series in Probability and Statistics. Chichester: Wiley. With a foreword by D.G. Kendall. · Zbl 0946.68144 [27] Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5. Oxford: Oxford Univ. Press. · Zbl 1029.60007 [28] Schneider, R. and Weil, W. (2008). Stochastic and Integral Geometry. Probability and Its Applications (New York). Berlin: Springer. · Zbl 1175.60003 [29] Schulte, M. and Thäle, C. (2016). Poisson point process convergence and extreme values in stochastic geometry. In Stochastic Analysis for Poisson Point Processes. Bocconi Springer Ser. 7 255-294. Bocconi Univ. Press. · Zbl 1528.60050 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.