{"id":182,"date":"2022-06-28T13:39:27","date_gmt":"2022-06-28T13:39:27","guid":{"rendered":"https:\/\/dccg.upc.edu\/topping\/?page_id=182"},"modified":"2022-06-28T13:39:27","modified_gmt":"2022-06-28T13:39:27","slug":"topping-midterm-meeting-invited-talk","status":"publish","type":"page","link":"https:\/\/dccg.upc.edu\/topping\/topping-midterm-meeting-invited-talk\/","title":{"rendered":"TOPPING midterm meeting &#8211; Invited talk"},"content":{"rendered":"\n<p><strong>Complexity Results on Untangling Red-Blue Matchings<\/strong><\/p>\n\n\n\n<p><strong><a href=\"https:\/\/pageperso.lis-lab.fr\/guilherme.fonseca\/\">Guilherme Dias da Fonseca<\/a><\/strong>, Aix-Marseille University<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>Abstract: <\/p>\n\n\n\n<p>Given a matching between n red points and n blue points by line<br>segments in the plane, we consider the problem of obtaining a<br>crossing-free matching through flip operations that replace two<br>crossing segments by two non-crossing ones. We first show that (i) it<br>is NP-hard to alpha-approximate the shortest flip sequence, for any<br>constant alpha. Second, we show that when the red points are colinear,<br>(ii) given a matching, a flip sequence of length at most n(n-1)\/2<br>always exists, and (iii) the number of flips in any sequence never<br>exceeds (n(n-1)\/2) (n+4)\/6. Finally, we present (iv) a lower bounding<br>flip sequence with roughly 1.5 n(n-1)\/2 flips, which shows that the<br>n(n-1)\/2 flips attained in the convex case are not the maximum, and<br>(v) a convex matching from which any flip sequence has roughly 1.5 n<br>flips. The last four results, based on novel analyses, improve the<br>constants of state-of-the-art bounds.<\/p>\n\n\n\n<p><a href=\"https:\/\/arxiv.org\/abs\/2202.11857\">Full version in arXiv<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 linesegments in the plane, we consider the problem of obtaining acrossing-free matching through flip operations that replace twocrossing segments by two non-crossing ones. We first show that (i) itis NP-hard [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-182","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/comments?post=182"}],"version-history":[{"count":1,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/182\/revisions"}],"predecessor-version":[{"id":183,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/182\/revisions\/183"}],"wp:attachment":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/media?parent=182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}