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 = {R₁, R₂, …, R_2n} 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]