When Crossings Count - Approximating the Minimum Spanning Tree

S. Har-Peled and P. Indyk

In the first part of the 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/µ⁵) alpha³⁽ⁿ) log⁵ n), where µ > 0 is a prescribed constant.

In the second part of our paper, we show how to embed such a crossing metric, into high-dimensions, so that the distances are preserved. As a result, we can deploy a large collection of subquadratic approximations algorithms \cite im-anntr-98,giv-rahdg-99 for problems involving points with the crossing metric as a distance function. Applications include matching, clustering, nearest-neighbor, and furthest-neighbor.

Appeared in The 16th Annu. ACM Sympos. Comput. Geom..

Postscript, PDF
Slides - html
Slides - star office

@string{SOCG16  = "Proc. 16th Annu. ACM Sympos. Comput. Geom."}

@inproceedings{hi-wccam-00,
  author =       {S.~Har-Peled and P.~Indyk},
  title =        {When Crossings Count - Approximating the Minimum
                  Spanning Tree},
  booktitle =    SOCG16,
  pages =        "166--175",
  year =         2000,
}

Last modified: Tue Jun 20 16:48:40 EDT 2000