The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension

Michiel Smid

We introduce the weak gap property for directed graphs whose vertex set $S$ is a metric space of size $n$. We prove that, if the doubling dimension of $S$ is a constant, any directed graph satisfying the weak gap property has $O(n)$ edges and total weight $O( \log n ) \cdot \wt(\MST(S))$, where $\wt(\MST(S))$ denotes the weight of a minimum spanning tree of $S$. We show that 2-optimal TSP tours and greedy spanners satisfy the weak gap property.