
arXiv: 2409.11614
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., 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.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Minimum Spanning Tree, Bichromatic Spanning Tree, Computer Science - Computational Geometry, Plane Tree, 004, ddc: ddc:004
Computational Geometry (cs.CG), FOS: Computer and information sciences, Minimum Spanning Tree, Bichromatic Spanning Tree, Computer Science - Computational Geometry, Plane Tree, 004, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
