2021/07/14 by H Le, Le, Hung, Cuong Than +1 · 2 citations
Computer Science · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #I.3.5 #Mathematical Dynamics and Fractals #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2107.06490
openalex publication_date 2021/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The greedy spanner in a low dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades as it possesses the two most basic properties of a good spanner: constant maximum degree and constant lightness. Recently, Eppstein and Khodabandeh showed that the greedy spanner in ℝ2 admits a sublinear separator in a strong sense: any subgraph of k vertices of the greedy spanner in ℝ2 has a separator of size O(√(k)). Their technique is inherently planar and is not extensible to higher dimensions. They left showing the existence of a small separator for the greedy spanner in ℝd for any constant d≥ 3 as an open problem. In this paper, we resolve the problem of Eppstein and Khodabandeh by showing that any subgraph of k vertices of the greedy spanner in ℝd has a separator of size O(k1-1/d). We introduce a new technique that gives a simple characterization for any geometric graph to have a sublinear separator that we dub τ-lanky: a geometric graph is τ-lanky if any ball of radius r cuts at most τ edges of length at least r in the graph. We show that any τ-lanky geometric graph of n vertices in ℝd has a separator of size O(τn1-1/d). We then derive our main result by showing that the greedy spanner is O(1)-lanky. We indeed obtain a more general result that applies to unit ball graphs and point sets of low fractal dimensions in ℝd. Our technique naturally extends to doubling metrics. We use the τ-lanky characterization to show that there exists a (1+ε)-spanner for doubling metrics of dimension d with a constant maximum degree and a separator of size O(n1-(1)/(d)); this result resolves an open problem posed by Abam and Har-Peled a decade ago.