When Crossings Count - Approximating the Minimum Spanning Tree

2003/03/01 by Har-Peled, Sariel, Indyk, Piotr
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5

paper · doi:10.48550/arxiv.cs/0303001

Abstract

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³(n) 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.

Related

• Approximating Spanning Trees with Low Crossing Number
• Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
• On the minimum spanning tree problem in imprecise set-up
• Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
• A characterization of minimum spanning tree-like metric spaces