2020/04/19 by Abu-Affash, A. Karim, Bhore, Sujoy, Carmi, Paz +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2004.08854
Given a set P of n red and blue points in the plane, a planar bichromatic spanning tree of P is a spanning tree of P, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree T, such that the length of the longest edge in T is minimized. In this paper, we show that this problem is NP-hard for points in general position. Moreover, we present a polynomial-time (8√(2))-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck λ can be converted to a planar bichromatic spanning tree of bottleneck at most 8√(2)λ.