On the expected maximum degree of Gabriel and Yao graphs

DOI10.1239/aap/1261669589zbMath1196.60019OpenAlexW2033513442MaRDI 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 graphmaximum degreeGabriel graphYao graph

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete geometry (52C99)

Related Items

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