Alternating paths and cycles of minimum length

Let R be a set of n red points and B be a set of n blue points in the Euclidean plane. We study the problem of computing a planar drawing of a cycle of minimum length that contains vertices at points R∪B and alternates colors. When these points are collinear, we describe a Θ(nlog⁡n)-time algorithm to find such a shortest alternating cycle where every edge has at most two bends. We extend our approach to compute shortest alternating paths in O(n2) time with two bends per edge and to compute shortest alternating cycles on 3-colored point sets in O(n2) time with O(n) bends per edge. We also prove that for arbitrary k-colored point sets, the problem of computing an alternating shortest cycle is NP-hard, where k is any positive integer constant.