When crossings count - approximating the minimum spanning tree

Sariel Har-Peled, Piotr Indyk

Research output: Contribution to conferencePaperpeer-review


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/ε53(n) log5 n), where ε>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, nearest-neighbor, and furthest-neighbor.

Original languageEnglish (US)
Number of pages10
StatePublished - 2000
Externally publishedYes
Event16th Annual Symposium on Computational Geometry - Hong Kong, Hong Kong
Duration: Jun 12 2000Jun 14 2000


Other16th Annual Symposium on Computational Geometry
CityHong Kong, Hong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'When crossings count - approximating the minimum spanning tree'. Together they form a unique fingerprint.

Cite this