SPANNERS OF COMPLETE k-PARTITE GEOMETRIC GRAPHS
We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in 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+ subset of)spanner of K with O(n) edges in O(n log n) time. The second algorithm computes a (3 + is an element of)-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 <= k <= n - circle minus(root 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.
spanners k-partite geometric graphs computational geometry