Planar Bichromatic Bottleneck Spanning Trees
share
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)λ.
READ FULL TEXT