Spanners of Complete $k$-Partite Geometric Graphs

Abstract

We address the following problem: Given a complete $k$-partite geometric graph $K$ whose vertex set is a set of $n$ points in ${\mathbb{R}}^d$, compute a spanner of $K$ that has a ``small'' stretch factor and ``few'' edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon )$-spanner of $K$ with O(n) edges in $O(n\log n)$ time. The second algorithm computes a $(3+\epsilon )$-spanner of $K$ with $O(n\log n)$ edges in $O(n\log n)$ time. The latter result is optimal: We show that for any $2\le k\le n-\Theta (\sqrt{n\log n})$, spanners with $O(n\log n)$ edges and stretch factor less than 3 do not exist for all complete $k$-partite geometric graphs.

References in corpus (1)

• Geometric Spanners With Small Chromatic Number

Cited by in corpus (1)

• Spanners of Additively Weighted Point Sets