Paper by Erik D. Demaine

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.

Given a set S = {R1R2, …, R2n} of 2n 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.

The abstract is 4 pages.

The abstract is available in PDF (266k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated September 3, 2017 by Erik Demaine.