**Reference**:- Greg Aloupis, Esther M. Arkin, David Bremner, Erik D. Demaine, Sándor P. Fekete, Bahram Kouhestani, and Joseph S. B. Mitchell, “Matching regions in the plane using non-crossing segments”, in
*Abstracts from the 16th Spanish Meeting on Computational Geometry (EGC 2015)*, Barcelona, Spain, July 1–3, 2015, to appear. **Abstract**:-
Given a set
*S*= {*R*_{1},*R*_{2}, …,*R*_{2n}} of 2*n*disjoint open regions in the plane, we examine the problem of computing a*non-crossing perfect region-matching*: a perfect matching on*S*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. **Length**:- The abstract is 4 pages.
**Availability**:- The abstract is available in PDF (266k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated October 28, 2020 by Erik Demaine.