On the expected maximum degree of Gabriel and Yao graphs. (English) Zbl 1196.60019
Summary: Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on \(n\) points drawn uniformly at random from a unit square grows as \(\Theta ( \log n / \log \log n)\) in probability.
MSC:
| 60D05 | Geometric probability and stochastic geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C99 | Discrete geometry |
References:
| [1] | Alon, N. and Spencer, J. H. (2000). The Probabilistic Method , 2nd edn. John Wiley, New York. · Zbl 0996.05001 |
| [2] | Barrière, L., Fraigniaud, P., Narayanan, L. and Opatrny, J. (2003). Robust position-based routeing in wireless ad hoc networks with irregular transmission range. Wireless Commun. Mobile Comput. 3 , 141–153. |
| [3] | Bern, M., Eppstein, D. and Yao, F. (1991). The expected extremes in a Delaunay triangulation. Internat. J. Comput. Geometry Appl. 1 , 79–91. · Zbl 0724.68084 · doi:10.1142/S0218195991000074 |
| [4] | Bose, P., Morin, P., Stojmenović, I. and Urrutia, J. (2001). Routeing with guaranteed delivery in ad hoc wireless networks. Wireless Networks 7 , 609–616. · Zbl 0996.68012 · doi:10.1023/A:1012319418150 |
| [5] | Chernoff, H. (1952). A measure of the asymptotic efficient of tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 , 493–507. · Zbl 0048.11804 · doi:10.1214/aoms/1177729330 |
| [6] | Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2006). Introduction to Algorithms , 2nd edn. MIT Press, Cambridge, Massachussets. · Zbl 1187.68679 |
| [7] | Devroye, L. (1988). The expected size of some graphs in computational geometry. Comput. Math. Appl. 15 , 53–64. · Zbl 0649.68066 · doi:10.1016/0898-1221(88)90071-5 |
| [8] | Gabriel, K. R. and Sokal, R. R. (1969). A new statistical approach to geographic variation analysis. Systematic Zoology 18 , 259–278. |
| [9] | Glick, N. (1978). Breaking records and breaking boards. Amer. Math. Monthly 85 , 2–26. JSTOR: · Zbl 0395.62040 · doi:10.2307/2978044 |
| [10] | Grünewald, M., Lukovszki, T., Schindelhauer, C. and Volbert, K. (2002). Distributed maintenance of resource efficient wireless network topologies. In Proc. 8th Internat. Euro-Par Conf. Parallel Processing , Springer, Berlin, pp. 935–946. · Zbl 1068.68544 |
| [11] | Karp, B. and Kung, H. T. (2000). GPSR: greedy perimeter stateless routeing for wireless networks. In Proc. 6th Annual Internat. Conf. Mobile Comput. Networking , ACM, New York, pp. 243–254. |
| [12] | Li, X.-Y., Wan, P.-J. and Wang, Y. (2001). Power efficient and sparse spanner for wireless ad hoc networks. In IEEE Internat. Conf. Computer Commun. Networks (ICCCN01) , Scottsdale, Arizona, pp. 564–567. |
| [13] | Matula, D. W. and Sokal, R. R. (1980). Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical Analysis 12 , 205–222. |
| [14] | Meester, R. and Roy, R. (1996). Continuum Percolation (Camb. Tracts Math. 119 ). Cambridge University Press. |
| [15] | Narasimhan, G. and Smid, M. (2007). Geometric Spanner Networks . Cambridge University Press. · Zbl 1140.68068 · doi:10.1017/CBO9780511546884 |
| [16] | Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5 ). Oxford University Press. · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001 |
| [17] | Penrose, M. D. and Yukich, Y. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Prob. 13 , 277–303. · Zbl 1029.60008 · doi:10.1214/aoap/1042765669 |
| [18] | Schindelhauer, C., Volbert, K. and Ziegler, M. (2007). Geometric spanners with applications in wireless networks. Comput. Geometry 36 , 197–214. · Zbl 1110.68156 · doi:10.1016/j.comgeo.2006.02.001 |
| [19] | Ta, X., Mao, G. and Anderson, B. D. O. (2009). On the phase transition width of \(K\)-connectivity in wireless multihop networks. IEEE Trans. Mobile Comput. 8 , 936–949. |
| [20] | Toussaint, G. T. (1980). Pattern recognition and geometrical complexity. In Proc. 5th Internat. Conf. Pattern Recognition , pp. 1324–1347. · Zbl 0437.05050 · doi:10.1016/0031-3203(80)90066-7 |
| [21] | Toussaint, G. T. (1980). The relative neighborhood graph of a finite planar set. Pattern Recognition 12 , 261–268. · Zbl 0437.05050 · doi:10.1016/0031-3203(80)90066-7 |
| [22] | Toussaint, G. T. (1982). Computational geometric problems in pattern recognition. In Pattern Recognition Theory and Applications (NATO Adv. Study Inst. Ser. C: Math. Phys. Sci. 81 ), Reidel, Dordrecht, eds J. Kittler, K. S. Fu, and L. F. Pau, pp. 73–91. · Zbl 0503.68068 |
| [23] | Wang, Y. and Li, X.-Y. (2006). Localized construction of bounded degree and planar spanner for wireless ad hoc networks. ACM Mobile Network Appl. 11 , 161–175. · Zbl 1132.90316 · doi:10.1007/s10878-006-5980-0 |
| [24] | Wattenhofer, R., Li, L., Bahl, P. and Wang, Y. (2001). Distributed topology control for wireless multihop ad hoc networks. In Proc. IEEE INFOCOM , pp. 1388–1397. |
| [25] | Yao, A. C.-C. (1982). On constructing minimum spanning trees in \(k\)-dimensional spaces and related problems. SIAM J. Comput. 11 , 721–736. · Zbl 0492.68050 · doi:10.1137/0211059 |
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.
