Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.comgeo.2012.04.005 | Comput. Geom. |
Keywords | Field | DocType |
Matching,Non-crossing,Geometric objects | Discrete mathematics,Line segment,Ordered set,Combinatorics,Polynomial,Convex polygon,Mathematics | Journal |
Volume | Issue | ISSN |
46 | 1 | 0925-7721 |
Citations | PageRank | References |
10 | 0.85 | 26 |
Authors | ||
13 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Greg Aloupis | 1 | 200 | 26.50 |
| Jean Cardinal | 2 | 335 | 47.57 |
| Sébastien Collette | 3 | 185 | 19.48 |
| Erik D. Demaine | 4 | 4624 | 388.59 |
| Martin L. Demaine | 5 | 592 | 84.37 |
| Muriel Dulieu | 6 | 27 | 3.80 |
| Ruy Fabila-MonroyDavid | 7 | 54 | 8.75 |
| Vi Hart | 8 | 12 | 1.62 |
| Ferran Hurtado | 9 | 744 | 86.37 |
| Stefan Langerman | 10 | 831 | 101.66 |
| Maria Saumell | 11 | 58 | 10.50 |
| Carlos Seara | 12 | 309 | 30.30 |
| Perouz Taslakian | 13 | 12 | 1.60 |