Name
Abstract | ||
|---|---|---|
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.ISAAC.2018.52 | ISAAC |
DocType | Volume | Citations |
Conference | abs/1809.10078 | 0 |
PageRank | References | Authors |
0.34 | 0 | 9 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vahideh Keikha | 1 | 1 | 2.85 |
| Mees van de Kerkhof | 2 | 1 | 0.70 |
| Marc J. van Kreveld | 3 | 1702 | 166.91 |
| Irina Kostitsyna | 4 | 33 | 18.08 |
| Maarten Löffler | 5 | 551 | 62.87 |
| Frank Staals | 6 | 29 | 11.40 |
| Jérôme Urhausen | 7 | 0 | 1.01 |
| Jordi L. Vermeulen | 8 | 2 | 1.71 |
| Lionov Wiratma | 9 | 16 | 3.22 |