2012/06/27 by Tillmann Miltzow, Miltzow, Tillmann
Computer Science · Engineering · #3D Shape Modeling and Analysis #Computational Geometry and Mesh Generation #Data Management and Algorithms #cs.CC #cs.CG
paper · pdf · doi:10.48550/arxiv.1206.6360
arxiv created 2012/06/27 · arxiv updated 2012/06/28
Given 2n points in the plane, it is well-known that there always exists a perfect straight-line non-crossing matching. We show that it is NP-complete to decide if a partial matching can be augmented to a perfect one, via a reduction from 1-in-3-SAT. This result also holds for bichromatic matchings.