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.

BibTeX

@InProceedings{MatchingRegions_EGC2015,
  AUTHOR        = {Greg Aloupis and Esther M. Arkin and David Bremner and Erik D. Demaine and S\'andor P. Fekete and Bahram Kouhestani and Joseph S. B. Mitchell},
  TITLE         = {Matching regions in the plane using non-crossing segments},
  BOOKTITLE     = {Abstracts from the 16th Spanish Meeting on Computational Geometry (EGC 2015)},
  bookurl       = {http://www-ma2.upc.es/egc15/?lang=en},
  ADDRESS       = {Barcelona, Spain},
  MONTH         = {July 1--3},
  YEAR          = 2015,
  PAGES         = {to appear},

  length        = {4 pages},
  unrefereed    = 1,
  paperkind     = {abstract},
  withstudent   = 1,
}

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]