Matching regions in the plane using non-crossing segments
Greg Aloupis, Esther M. Arkin, David Avis, Erik D. Demaine, Bahram Kouhestani, Joseph S. B. Mitchell · 2015
In memory of our friend, Ferran Hurtado. Given a set S = fR1;R2;:::;R2ng of 2n disjoint open regions in the plane, we examine the problem of computing a non-crossing perfect region-matching: a perfect matching onS that is realized by a set of non-crossing line segments, with the segments disjoint from the regions. We study the complexity of this problem, showing that, in general, it is NP-hard. We also show that a perfect matching always exists and can be computed in polynomial time if the regions are unit (or more generally, nearly equal-size) disks or squares. We also consider the bipartite version of the problem in which there are n red regions and n blue regions; in this case, the problem is NP-hard even for unit disk (or unit square) regions.