Minimum Plane Bichromatic Spanning Trees
<|reference_start|>Minimum Plane Bichromatic Spanning Trees: For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in $O(n\log n)$ time where $n$ is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings.   Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of $O(\sqrt{n})$. It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an $O(\log n)$-factor approximation algorithm for the general case.<|reference_end|>
@article{akitaya2024minimum,
    title={Minimum Plane Bichromatic Spanning Trees},
    author={Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist,
  Frederick Stock, Csaba D. T'oth},
    journal={arXiv preprint arXiv:2409.11614},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.11614},
    primaryClass={cs.CG}
}