pith. sign in

arxiv: 2604.09248 · v1 · submitted 2026-04-10 · 🧮 math.PR · math.CO

Limit laws for longest edges in empty region graphs

Holger Sambale , Matthias Schulte , Christoph Thaele This is my paper

Pith reviewed 2026-05-10 17:18 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords empty region graphsPoisson point processlongest edgesGumbel distributionpoint process convergenceGabriel graphextreme value theory
0
0 comments X

The pith

As Poisson point intensity grows, longest edges in empty region graphs converge after scaling to a Gumbel distribution, with their midpoints and directions forming a limiting Poisson process.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Empty region graphs connect two points by an edge only when a prescribed region between them holds no other points. The paper examines these graphs on a stationary Poisson point process in d-dimensional space. It proves that as the process intensity tends to infinity, the point process of edge midpoints together with suitably transformed edge lengths and directions converges in distribution to a Poisson process on R^d times R times the space of lines through the origin. The transformed length of the longest edge whose midpoint lies inside a fixed observation window converges in distribution to a Gumbel random variable. The proofs supply explicit error bounds in Kantorovich-Rubinstein distance for the point-process approximation and in Kolmogorov distance for the maximum length, and the same statements hold uniformly for the Gabriel graph, relative-neighbourhood graph, beta-skeleton, Mastercard graph and Pacman graph.

Core claim

Letting the intensity of the underlying Poisson process tend to infinity, we consider the associated point process of edge midpoints, suitably transformed edge lengths, and directions of the edges. We prove that it converges in distribution to a Poisson process on R^d × R × L^d, and that the suitably transformed length of the longest edge with midpoint in an observation window converges in distribution to a Gumbel distributed random variable. Our approach yields explicit error bounds in Kantorovich-Rubinstein distance for the point process convergence when restricting to an observation window and in Kolmogorov distance for the maximal edge length. The results apply uniformly to a broad class

What carries the argument

The marked point process of edge midpoints, transformed lengths, and directions that is shown to converge to a Poisson process on R^d × R × L^d

If this is right

  • The length of the longest edge inside any fixed window, after the paper's scaling, converges in distribution to a Gumbel random variable.
  • Explicit quantitative bounds control the distance between the finite-intensity edge point process and its Poisson limit.
  • The same limiting statements hold simultaneously for the Gabriel graph, the relative neighbourhood graph, the beta-skeleton, the Mastercard graph and the Pacman graph.
  • The convergence statements remain valid when attention is restricted to edges whose midpoints fall inside a given observation window.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The uniform convergence across region definitions suggests that extreme-value statistics for edge lengths may be insensitive to moderate changes in the empty-region rule.
  • The explicit error bounds make it possible to calibrate simulation sizes needed to reach a prescribed accuracy for the Gumbel approximation.
  • Similar point-process techniques could be tested on other spatial graphs whose edges are forbidden by local emptiness conditions, such as certain models of wireless ad-hoc networks.

Load-bearing premise

The defining regions of the different empty region graphs share enough geometric structure that identical scaling and convergence arguments apply to all of them simultaneously.

What would settle it

Simulations of the Gabriel graph on Poisson points of steadily increasing intensity in which the distribution of the longest suitably transformed edge length fails to approach the Gumbel cumulative distribution function would falsify the claimed convergence.

Figures

Figures reproduced from arXiv: 2604.09248 by Christoph Thaele, Holger Sambale, Matthias Schulte.

Figure 1
Figure 1. Figure 1: The Gabriel graph (left), the strong nearest neighbour graph (middle), and the relative [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The beta-skeleton graph with β = 5 (left), the Mastercard graph (middle), and the truncated slab graph (right) generated by the same set of points. literature, mostly in the plane, cf. [1, 5, 8, 9, 12, 14, 17, 18]. Simulations of these graphs are shown in Figures 1–3, while illustrations of the regions S(x, y) are provided in Figures 4–6. Example 1.1 (Gabriel graph). Let S(x, y) := Bd ((x + y)/2, ∥x − y∥/2… view at source ↗
Figure 3
Figure 3. Figure 3: The generalised Gabriel graph with K = [−1/2, 1/2]2 (left), K = conv{(−1/2, 0),(1/2, 0),(0, 1/2)} (middle), and K an axis-aligned ellipse with semi axes 1/2 and 3/10 (right) generated by the same set of points. x y x y x y [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Two points x, y and the regions S(x, y) for the Gabriel graph (left), the strong nearest neighbour graph (middle), and the relative neighbourhood graph (right). Example 1.8 (Generalised Gabriel graph). Let S(x, y) be of the form S(x, y) = x + y 2 + ∥x − y∥K, where K ⊂ R d is a compact set that has non-empty interior and is star-shaped (i.e., [0z] ⊂ K for all z ∈ K). The resulting empty region graph GS(ηt) … view at source ↗
Figure 5
Figure 5. Figure 5: Two points x, y and the regions S(x, y) for the beta-skeleton graph with β = 3 (left) and the Mastercard graph (right). To measure the distance between two point processes ξ and ζ on X such that E[ξ(X)],E[ζ(X)] < ∞, we use the Kantorovich–Rubinstein distance. It is defined as dKR(ξ, ζ) := supn E[h(ξ)] − E[h(ζ)] [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Two points x, y and the regions S(x, y) for the Pacman graph with β = π/2 (left), the truncated slab graph (middle), and the generalised Gabriel graph with K = [−1/2, 1/2]2 (right). for any t ≥ 2. Here, c ∈ (0, ∞) is a constant which only depends on d, vol(W), b, and the parameters of the particular example. Note that the parameters of the particular examples that affect the constant in the previous theore… view at source ↗
read the original abstract

Empty region graphs are graphs whose vertices are points in $\mathbb{R}^d$ and where two vertices are connected by an edge whenever some associated region does not contain any other vertices. We investigate the asymptotic behaviour of long edges in empty region graphs generated by a stationary Poisson process in $\mathbb{R}^d$. {Letting} the intensity of the underlying Poisson process tend to infinity, we consider the associated point process of edge midpoints, suitably transformed edge lengths, and directions of the edges. We prove that it converges in distribution to a Poisson process on $\mathbb{R}^d \times \mathbb{R}\times\mathbb{L}^d$, where $\mathbb{L}^d$ is the space of lines in $\mathbb{R}^d$ through the origin, and that the suitably transformed length of the longest edge with midpoint in an observation window converges in distribution to a Gumbel distributed random variable. Our approach yields explicit error bounds in Kantorovich--Rubinstein distance for the point process convergence {when restricting to an observation window} and in Kolmogorov distance for the maximal edge length. The results apply uniformly to a broad class of empty region graphs, including the Gabriel graph, the relative neighbourhood graph, the beta-skeleton graph, the Mastercard graph, and the Pacman graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper investigates the asymptotic behavior of long edges in empty region graphs generated by a stationary Poisson process in R^d. As the intensity tends to infinity, the point process consisting of edge midpoints, transformed edge lengths, and directions converges in distribution to a Poisson process on R^d × R × L^d. The suitably transformed length of the longest edge with midpoint in an observation window converges to a Gumbel random variable. Explicit error bounds are given in Kantorovich-Rubinstein distance for the point process convergence and in Kolmogorov distance for the maximal edge length. These results apply uniformly to the Gabriel graph, relative neighbourhood graph, beta-skeleton graph, Mastercard graph, and Pacman graph.

Significance. This work offers a unified treatment of extreme value statistics for a family of proximity graphs in stochastic geometry. The provision of explicit quantitative bounds on the convergence rates is a notable strength, as it facilitates practical applications where approximation accuracy is important. If the uniformity across the different empty region definitions holds, it represents a significant advance over graph-specific analyses.

major comments (2)
  1. [§3 (General framework)] §3 (General framework): The proof of uniform convergence relies on the volume functions of the empty regions satisfying identical regularity conditions (e.g., monotonicity in length and integrability over directions). For the Pacman graph, the defining region is a half-disk with a specific angle, leading to a volume function that differs in its angular dependence from the diametral ball of the Gabriel graph; it is not immediately clear from the statement whether the constants in the Kantorovich-Rubinstein bound remain uniform without graph-specific adjustments.
  2. [Theorem 4.2 (Gumbel limit)] Theorem 4.2 (Gumbel limit): The reduction from the Poisson process limit to the Gumbel distribution for the maximum assumes that the intensity measure factors in a way that the length coordinate has an exponential tail uniformly. Verify that the transformation of the edge length is chosen identically for all graphs, as the scaling may depend on the specific volume growth rate.
minor comments (2)
  1. [Notation] Notation: The space L^d is defined as the space of lines through the origin; clarify if it is equipped with the invariant measure or the Grassmannian measure.
  2. [Introduction] Introduction: Some references to prior work on empty region graphs could be expanded to include recent results on their connectivity properties.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments. We address each point below, providing clarifications based on the general framework developed in the manuscript. We will incorporate revisions to make the uniformity explicit.

read point-by-point responses

  1. Referee: §3 (General framework): The proof of uniform convergence relies on the volume functions of the empty regions satisfying identical regularity conditions (e.g., monotonicity in length and integrability over directions). For the Pacman graph, the defining region is a half-disk with a specific angle, leading to a volume function that differs in its angular dependence from the diametral ball of the Gabriel graph; it is not immediately clear from the statement whether the constants in the Kantorovich-Rubinstein bound remain uniform without graph-specific adjustments.

    Authors: In Section 3 we define the general framework via regularity conditions on the volume functions (monotonicity in the length parameter and uniform integrability over directions) that are satisfied by all graphs in the family, including the Pacman graph. Although the angular dependence differs for the Pacman half-disk, its volume function remains comparable to that of the Gabriel graph up to constants bounded away from zero and infinity independently of the specific graph (owing to the fixed positive angle). Consequently the Kantorovich-Rubinstein bounds derived from these conditions are uniform across the class without graph-specific adjustments. We will add an explicit verification paragraph in Section 3 confirming that the constants remain uniform for the Pacman graph. revision: yes

  2. Referee: Theorem 4.2 (Gumbel limit): The reduction from the Poisson process limit to the Gumbel distribution for the maximum assumes that the intensity measure factors in a way that the length coordinate has an exponential tail uniformly. Verify that the transformation of the edge length is chosen identically for all graphs, as the scaling may depend on the specific volume growth rate.

    Authors: The length transformation is defined uniformly in the general framework of Section 3 so that the intensity measure on the transformed length coordinate has density proportional to e^{-x} dx, independent of the particular empty-region graph. This is possible because the volume functions of all considered graphs (Gabriel, relative neighbourhood, beta-skeleton, Mastercard, Pacman) satisfy the same monotonicity and integrability conditions, which imply that their growth rates are asymptotically equivalent up to uniform constants. The proof of Theorem 4.2 therefore applies verbatim to the whole family. We will add a clarifying sentence in the statement of Theorem 4.2 stating that the same transformation is used for all graphs. revision: yes

Circularity Check

0 steps flagged

No circularity: standard probabilistic convergence proofs for Poisson-driven graphs

full rationale

The paper derives distributional limits and error bounds for longest edges in empty region graphs via coupling and Stein-method arguments applied to a stationary Poisson point process. These are first-principles stochastic-geometry results that do not reduce any claimed prediction or limit to a fitted parameter, self-defined quantity, or load-bearing self-citation. The uniformity claim across graph families rests on shared regularity conditions on the empty regions, which are stated as assumptions rather than derived from the target conclusion. No step equates an output to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard properties of stationary Poisson point processes and point process convergence theorems; no free parameters, invented entities, or ad-hoc axioms introduced.

axioms (2)
  • standard math Stationary Poisson point process in R^d
    Underlying random point set whose intensity tends to infinity.
  • standard math Convergence criteria for marked point processes
    Used to establish the limiting Poisson process on the product space.

pith-pipeline@v0.9.0 · 5524 in / 1151 out tokens · 50707 ms · 2026-05-10T17:18:29.335065+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Arya and D.M

    S. Arya and D.M. Mount (2018): Computational Geometry: Proximity and Location. In: Hand- book of Data Structures and Applications. 2nd edition. Chapman and Hall/CRC

    work page 2018

  2. [2]

    Barbour, L

    A.D. Barbour, L. Holst, and S. Janson (1992).Poisson Approximation. Oxford University Press. 23

    work page 1992

  3. [3]

    Bobrowski, M

    O. Bobrowski, M. Schulte, and D. Yogeshwaran (2022). Point process approximation under sta- bilization and Palm coupling. Ann. Henri Lesbesgue5, 1489–1534

    work page 2022

  4. [4]

    Calka and N

    P. Calka and N. Chenavier (2014). Extreme values for characteristic radii of a Poisson-Voronoi tessellation. Extremes17, 359–385

    work page 2014

  5. [5]

    Cardinal, S

    J. Cardinal, S. Collette, and S. Langerman (2009). Empty region graphs. Comput. Geom.42, 183–195

    work page 2009

  6. [6]

    Chenavier, N

    N. Chenavier, N. Henze, and M. Otto (2022). Limit laws for largekth-nearest neighbor balls. J. Appl. Probab.59, 880–894

    work page 2022

  7. [7]

    Decreusefond, M

    L. Decreusefond, M. Schulte, and C. Thäle (2016). Functional Poisson approximation in Kantorovich–Rubinstein distance with applications to U-statistics and stochastic geometry. Ann. Probab.44, 2147–2197

    work page 2016

  8. [8]

    Devillers and C

    O. Devillers and C. Duménil (2021). Stochastic analysis of empty-region graphs. CCCG 2021 – 33rd Canadian Conference on Computational Geometry, Halifax/Virtual, Canada

    work page 2021

  9. [9]

    Devroye (1988)

    L. Devroye (1988). The expected size of some graphs in computational geometry. Comput. Math. Appl.15, 53–64

    work page 1988

  10. [10]

    Goldstein, T

    L. Goldstein, T. Johnson, and R. Lachièze-Rey (2018). Bounds to the normal for proximity region graphs. Stochastic Process. Appl.128, 1208–1237

    work page 2018

  11. [11]

    weighted

    N. Henze (1982). The limit distribution for maxima of “weighted”rth-nearest-neighbour distances. J. Appl. Probab.19, 344–354

    work page 1982

  12. [12]

    Jaromczyk and G

    J. Jaromczyk and G. Toussaint (1992). Relative neighborhood graphs and their relatives. Pro- ceedings of the IEEE80, 1502–1571

    work page 1992

  13. [13]

    Kallenberg (2021).Foundations of Modern Probability

    O. Kallenberg (2021).Foundations of Modern Probability. 3rd edition. Springer

    work page 2021

  14. [14]

    Kirkpatrick and J.D

    D.G. Kirkpatrick and J.D. Radke (1985). A framework for computational morphology. InCom- putational Geometry(edited by G.T. Toussaint), 217–248, North-Holland

    work page 1985

  15. [15]

    Last and M

    G. Last and M. Penrose (2017).Lectures on the Poisson Process. Cambridge University Press

    work page 2017

  16. [16]

    Lee (1985)

    D.T. Lee (1985). Relative neighbourhood graphs in theℓ1-metric. Pattern Recognition18, 327– 332

    work page 1985

  17. [17]

    Mathieson and P

    L. Mathieson and P. Moscato (2019). An Introduction to Proximity Graphs. In:Business and Consumer Analytics: New Ideas, Springer

    work page 2019

  18. [18]

    Mitchell and W

    J.S.B. Mitchell and W. Mulzer (2017). Proximity algorithms. In:Handbook of Discrete and Com- putational Geometry, 3rd edition, 849–874

    work page 2017

  19. [19]

    Otto (2025)

    M. Otto (2025). Poisson approximation of Poisson-driven point processes and extreme values in stochastic geometry. Bernoulli31, 30–54

    work page 2025

  20. [20]

    Penrose (1997)

    M.D. Penrose (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7, 340–361

    work page 1997

  21. [21]

    Ross (2011)

    N. Ross (2011). Fundamentals of Stein’s method. Probability Surveys8, 210–293

    work page 2011

  22. [22]

    Rousselle and E

    A. Rousselle and E. Sönmez (2024). The longest edge in discrete and continuous long-range per- colation. Extremes27, 673–703. 24

    work page 2024

  23. [23]

    Stochastic Models40, 399–416

    A.RousselleandE.Sönmez(2024).Thelongestedgeoftheone-dimensionalsoftrandomgeometric graph with boundaries. Stochastic Models40, 399–416

    work page 2024

  24. [24]

    Schneider and W

    R. Schneider and W. Weil (2008).Stochastic and Integral Geometry. Springer

    work page 2008

  25. [25]

    Schymura (2011).Probabilistic Matching of Solid Shapes in Arbitrary Dimension

    D. Schymura (2011).Probabilistic Matching of Solid Shapes in Arbitrary Dimension. PhD thesis, FU Berlin, available athttps://refubium.fu-berlin.de/handle/fub188/6048

    work page 2011

  26. [26]

    Toussaint (1980)

    G.T. Toussaint (1980). The relative neighbourhood graph of a finite planar set. Pattern Recogni- tion12, 261–268. 25

    work page 1980