Non-crossing matchings of points with 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 p...
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99978 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826202986851860480 |
|---|---|
| author | 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 |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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 |
| author_sort | Aloupis, Greg |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:29:20Z |
| format | Article |
| id | mit-1721.1/99978 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:29:20Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/999782022-10-01T09:17:07Z 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 Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Martin L. 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. Project MTM2009-07242 Gen. Cat. DGR 2009SGR1040 Association pour le developpement de la recherche sur le cancer (France) European Science Foundation (EUROCORES programme EuroGIGA) Belgian National Foundation for Scientific Research (EUROGIGA NR 13604) Belgian National Foundation for Scientific Research (MICINN Project EUI-EURC-2011-4306) 2015-11-23T13:33:29Z 2015-11-23T13:33:29Z 2012-04 2012-04 Article http://purl.org/eprint/type/JournalArticle 09257721 http://hdl.handle.net/1721.1/99978 Aloupis, Greg, Jean Cardinal, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila-Monroy, et al. “Non-Crossing Matchings of Points with Geometric Objects.” Computational Geometry 46, no. 1 (January 2013): 78–92. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1016/j.comgeo.2012.04.005 Computational Geometry Creative Commons Attribution-Noncommercial-NoDerivatives http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier MIT web domain |
| spellingShingle | 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 Non-crossing matchings of points with geometric objects |
| title | Non-crossing matchings of points with geometric objects |
| title_full | Non-crossing matchings of points with geometric objects |
| title_fullStr | Non-crossing matchings of points with geometric objects |
| title_full_unstemmed | Non-crossing matchings of points with geometric objects |
| title_short | Non-crossing matchings of points with geometric objects |
| title_sort | non crossing matchings of points with geometric objects |
| url | http://hdl.handle.net/1721.1/99978 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT aloupisgreg noncrossingmatchingsofpointswithgeometricobjects AT cardinaljean noncrossingmatchingsofpointswithgeometricobjects AT collettesebastien noncrossingmatchingsofpointswithgeometricobjects AT demaineerikd noncrossingmatchingsofpointswithgeometricobjects AT demainemartinl noncrossingmatchingsofpointswithgeometricobjects AT dulieumuriel noncrossingmatchingsofpointswithgeometricobjects AT fabilamonroyruy noncrossingmatchingsofpointswithgeometricobjects AT hartvi noncrossingmatchingsofpointswithgeometricobjects AT hurtadoferran noncrossingmatchingsofpointswithgeometricobjects AT langermanstefan noncrossingmatchingsofpointswithgeometricobjects AT saumellmaria noncrossingmatchingsofpointswithgeometricobjects AT searacarlos noncrossingmatchingsofpointswithgeometricobjects AT taslakianperouz noncrossingmatchingsofpointswithgeometricobjects |