Non-crossing matchings of points with geometric objects

详细信息    查看全文

• 作者：Greg Aloupis ; Jean Cardinal ; S¨¦bastien Collette ; Erik D. Demaine ; Martin L. Demaine ; Muriel Dulieu ; Ruy Fabila-Monroy ; Vi Hart ; Ferran Hurtado ; Stefan Langerman ; Maria Saumell ; Carlos Seara ; Perouz Taslakian
• 关键词：Matching ; Non-crossing ; Geometric objects
• 刊名：Computational Geometry
• 出版年：2013
• 出版时间：January, 2013
• 年：2013
• 卷：46
• 期：1
• 页码：78-92
• 全文大小：351 K

文摘

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.