论文标题
复杂性导致无缠绕的红蓝色匹配
Complexity Results on Untangling Red-Blue Matchings
论文作者
论文摘要
鉴于平面中的n红点和n个蓝点之间的匹配，我们考虑了通过翻转操作获得无交叉匹配的问题，这些操作将两个交叉段替换为两个非交叉段的问题。我们首先表明（i）对于任何恒定的alpha而言，它是alpha-approximate的最短翻转序列。其次，我们表明，当红点为colinear时，（ii）给定匹配，最多始终存在n（n-1）/2的长度的翻转序列，并且（iii）任何序列中的翻转数量永远不会超过（n（n+4）（n+4）/6。最后，我们呈现（iv）一个大约1.5 n（n-1）/2翻转的下边界翻转序列，这表明在凸状情况下获得的N（n（n-1）/2翻转不是最大值，并且（v）凸匹配的任何flip序列都具有大约1.5 n n的flips。基于新的分析，最后四个结果改善了最新界限的常数。
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.
