Let $P$ be a set of $N$ points in $\mathbb{R}^d$. For any $t \geq 1$, a $t$-spanner is an undirected graph $G=(P, E)$ weighted under the Euclidian measure, such that for any two points $v$, $u$, the shortest distance in $G$, $d(v, u)$, is at most $t$ times the Euclidian distance between $v$ and $u$, $|v u|$ (note that this definition can easily be extended to arbitrary measure spaces).

Consider the following algorithm with $P$ and $t$ as input:

E = empty
for every pair of points (v, u) in ascending order under |vu|
    if the shortest path in (P, E) is more than t times |vu|
        add (v, u) to E
return E

This algorithm computes the so-called greedy spanner (or path-greedy spanner). This graph has been subject to considerable research: it produces extremely good spanners, both in practice and in theory.

I'm interested in the length of the longest edge in the greedy spanner if $P$ is uniformly distributed in $[0,1]^d$ (the case that d=2 is fine as well). I conjecture this maximal length is at most about $1 / \sqrt{N}$, potentially with some log factors and factors $d$. This conjecture is motivated by experimental data.

The reason for my interest is that I have an algorithm that computes the greedy spanner quickly if the length of the longest edge is relatively short. If the above is correct, then it would mean my algorithm is applicable to the above scenario, and therefore potentially useful in practice.

I have found some papers analyzing the number of edges and the degree of other types of spanners on randomly distributed pointsets, but none on the length of the longest edge. The probability theory involved seemed rather complicated, so I was hoping something was known before attempting a proof myself.


1 Answer 1


In our paper Distribution-Sensitive Construction of the Greedy Spanner (accepted for ESA 2014) we prove the following (combining Theorem 4 and Lemma 6):

There exists $c_t$ dependent only on $t$ such that for every $c > 0$, if $P$ is a set of points uniformly and independently distributed at random in a $\sqrt{n} \times \sqrt{n}$ square and $n$ is large enough, then with probability at least $1 - n^c$, the greedy $t$-spanner on $P$ does not have edges longer than $c \cdot c_t \log n$.

Our bound on $c_t$ is fairly large, but we have experimental evidence that the 'right' bound is $\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.