Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Fabila Monroy, Ruy; Dulieu, Muriel; Hart, Vi; Hurtado Diaz, Fernando Alfredo; Langerman, Stefan; Saumell, Maria; Seara Ojea, Carlos; Taslakian, Perouz
Computational geometry: theory and applications
Vol. 46, num. 1, p. 78-92
DOI: 10.1016/j.comgeo.2012.04.005
Date of publication: 2013-01
Journal article
Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point–object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point–object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.