Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-24T05:07:54.530Z Has data issue: false hasContentIssue false
  • English
  • Français

On the expected maximum degree of Gabriel and Yao graphs

Part of: Discrete geometry Geometric probability and stochastic geometry

Published online by Cambridge University Press:  01 July 2016

Luc Devroye ,
Joachim Gudmundsson  and
Pat Morin
Luc Devroye*
Affiliation:
McGill University
Joachim Gudmundsson*
Affiliation:
NICTA
Pat Morin*
Affiliation:
Carleton University
*
∗ Postal address: School of Computer Science, McGill University, 3480 University Street, Montreal, Québec, H3A 2A7, Canada.
∗∗ Postal address: NICTA, School of IT Building, J12 1 Cleveland Street, University of Sydney, NSW 2006, Australia.
∗∗∗ Postal address: School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 Θ (log n / log log n) in probability.

Keywords

Random geometric graphGabriel graphYao graphmaximum degree

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 68U05: Computer graphics; computational geometry 52C99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 41 , Issue 4 , December 2009 , pp. 1123 - 1140
Copyright
Copyright © Applied Probability Trust 2009 

References

Alon, N. and Spencer, J. H. (2000). The Probabilistic Method, 2nd edn. John Wiley, New York.Google Scholar
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.CrossRefGoogle Scholar
Bern, M., Eppstein, D. and Yao, F. (1991). The expected extremes in a Delaunay triangulation. Internat. J. Comput. Geometry Appl. 1, 79–91.Google Scholar
Bose, P., Morin, P., Stojmenović, I. and Urrutia, J. (2001). Routeing with guaranteed delivery in ad hoc wireless networks. Wireless Networks 7, 609–616.Google Scholar
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.Google Scholar
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2006). Introduction to Algorithms, 2nd edn. MIT Press, Cambridge, Massachussets.Google Scholar
Devroye, L. (1988). The expected size of some graphs in computational geometry. Comput. Math. Appl. 15, 53–64.Google Scholar
Gabriel, K. R. and Sokal, R. R. (1969). A new statistical approach to geographic variation analysis. Systematic Zoology 18, 259–278.Google Scholar
Glick, N. (1978). Breaking records and breaking boards. Amer. Math. Monthly 85, 2–26.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
Meester, R. and Roy, R. (1996). Continuum Percolation (Camb. Tracts Math. 119). Cambridge University Press.Google Scholar
Narasimhan, G. and Smid, M. (2007). Geometric Spanner Networks. Cambridge University Press.Google Scholar
Penrose, M. (2003). Random Geometric Graphs (Oxford Stud. Prob. 5). Oxford University Press.CrossRefGoogle Scholar
Penrose, M. D. and Yukich, Y. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Prob. 13, 277–303.Google Scholar
Schindelhauer, C., Volbert, K. and Ziegler, M. (2007). Geometric spanners with applications in wireless networks. Comput. Geometry 36, 197–214.Google Scholar
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.Google Scholar
Toussaint, G. T. (1980). Pattern recognition and geometrical complexity. In Proc. 5th Internat. Conf. Pattern Recognition, pp. 1324–1347.Google Scholar
Toussaint, G. T. (1980). The relative neighborhood graph of a finite planar set. Pattern Recognition 12, 261–268.Google Scholar
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 Kittler, J., Fu, K. S., and Pau, L. F., pp. 73–91.Google Scholar
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.Google Scholar
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.Google Scholar
Yao, A. C.-C. (1982). On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721–736.Google Scholar