Complexity Results on Untangling Red-Blue Matchings
| Autor: | Das, Arun Kumar, Das, Sandip, da Fonseca, Guilherme D., Gerard, Yan, Rivier, Bastien |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 28 pages, 27 figures, accepted at EuroCG 2022, at CORE 2022 (ICALP Workshop), at LATIN 2022, and at CGTA 2022 (EuroCG 2022 special issue) |
| Databáze: | arXiv |
| Externí odkaz: |
|