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
DOIAbstract
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 mi...
Add to ORKG