Complexity Results on Untangling Red-Blue Matchings
Guilherme Dias da Fonseca, Aix-Marseille University
Abstract:
Given a matching between n red points and n blue points by line
segments in the plane, we consider the problem of obtaining a
crossing-free matching through flip operations that replace two
crossing segments by two non-crossing ones. We first show that (i) it
is NP-hard to alpha-approximate the shortest flip sequence, for any
constant alpha. Second, we show that when the red points are colinear,
(ii) given a matching, a flip sequence of length at most n(n-1)/2
always exists, and (iii) the number of flips in any sequence never
exceeds (n(n-1)/2) (n+4)/6. Finally, we present (iv) a lower bounding
flip sequence with roughly 1.5 n(n-1)/2 flips, which shows that the
n(n-1)/2 flips attained in the convex case are not the maximum, and
(v) a convex matching from which any flip sequence has roughly 1.5 n
flips. The last four results, based on novel analyses, improve the
constants of state-of-the-art bounds.