2015/09/18 by Bereg, Sergey, Fleszar, Krzysztof, Kindermann, Philipp +3 · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1509.05681
Given a set of k-colored points in the plane, we consider the problem of finding k trees such that each tree connects all points of one color class, no two trees cross, and the total edge length of the trees is minimized. For k=1, this is the well-known Euclidean Steiner tree problem. For general k, a kρ-approximation algorithm is known, where ρ≤ 1.21 is the Steiner ratio. We present a PTAS for k=2, a (5/3+ε)-approximation algorithm for k=3, and two approximation algorithms for general~k, with ratios O(√ n log k) and k+ε.