Matching points with things
Perouz Taslakian, Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila‐Monroy, Vi Hart, Ferrán Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · 2010
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. 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 number 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. © 2010 Springer-Verlag.