On the expected maximum degree of Gabriel and Yao graphs

DOI10.1239/aap/1261669589zbMath1196.60019MaRDI QIDQ3558941

Joachim Gudmundsson, Pat Morin, Luc P. Devroye

Publication date: 11 May 2010

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1239/aap/1261669589

zbMATH Keywords

random geometric graph; maximum degree; Gabriel graph; Yao graph

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

52C99: Discrete geometry

Related Items

PROXIMITY GRAPHS: E, δ, Δ, χ AND ω, Distribution-sensitive construction of the greedy spanner, On the number of higher order Delaunay triangulations, Connected spatial networks over random points and a route-length statistic, Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions, 10-Gabriel graphs are Hamiltonian

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum power assignment in wireless ad hoc networks with spanner property
• Geometric spanners with applications in wireless networks
• The expected size of some graphs in computational geometry
• The relative neighbourhood graph of a finite planar set
• Weak laws of large numbers in geometric probability
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• Geometric Spanner Networks
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Breaking Records and Breaking Boards
• Random Geometric Graphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Routing with guaranteed delivery in ad hoc wireless networks