Alternating paths and cycles of minimum length (Q340546)

Let \(R\) (red) and \(B\) (blue) be disjoint sets of points in the plane, each containing \(n\) points. An alternating cycle is a cycle graph drawn in the plane with vertex set \(R\cup B\) such that the endpoints of each edge have a different color. An alternating path may also be similarly defined. The length of a cycle or a path is the sum of its edge lengths. Only planar graphs are considered: edges are not allowed to cross. The authors present an algorithm for computing a planar alternating cycle of smallest possible length, in the case when the points of \(R\cup B\) are collinear, in \(\Theta(n\log{n})\) time. This algorithm is modified to compute a planar alternating path of minimal length in \(O(n^2)\) time, again assuming that points are collinear. For the case of 3 disjoint sets of points whose union is collinear, the authors give a \(O(n^2)\) time algorithm for computing a planar alternating cycle of minimum length. In contrast, for any number of disjoint sets that are not collinear, finding the shortest length planar alternating cycle is shown to be NP-hard.