Paper by Erik D. Demaine

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 = {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.

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.
These pages are generated automagically from a BibTeX file.
Last updated September 3, 2017 by Erik Demaine.