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 Rdbl; 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+ε)- spanner of K with O(n) edges in O(n log n) time. The second algorithm computes a (3 + ε)-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 - Θ( √ 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.
|Keywords||Computational geometry, K-partite geometric graphs, Spanners|
|Journal||SIAM Journal on Computing|
Bose, P, Carmi, P. (Paz), Couture, M. (Mathieu), Maheshwari, A, Morin, P, & Smid, M. (2008). Spanners of complete k-partite geometric graphs. SIAM Journal on Computing, 38(5), 1803–1820. doi:10.1137/070707130