When crossings count — approximating the minimum spanning tree
Sariel Har-Peled, Piotr Indyk · 2000
In this paper, we present an (1 + ¢)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings between the spanning tree and the lines.The expected running time is O ((n/e5)a 3 (n) log 5 n), where c > 0 is a prescribed constant.In the second part of our paper, we show how to embed such a crossing metric of hyperplanes in d-dimensions, in subquadratic time, into high-dimensions, so that the distances are preserved.As a result, we can deploy a large collection of subquadratic approximations algorithms [IM98, GIV99] for problems involving points with the crossing metric as a distance function.Applications include MST, matching, clustering, nearestneighbor, and furthest-neighbor.