Non-crossing matchings of points with geometric objects

作者：Aloupis Greg; Cardinal Jean; Collette Sebastien; Demaine Erik D; Demaine Martin L; Dulieu Muriel; Fabila Monroy Ruy; Hart Vi; Hurtado Ferran; Langerman Stefan; Saumell Maria; Seara Carlos; Taslakian Perouz^*

来源：Computational Geometry-Theory and Applications, 2013, 46(1): 78-92.

DOI：10.1016/j.comgeo.2012.04.005

• Matching
• Non-crossing
• Geometric objects

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.

• 出版日期2013-1