| Title: |
Convex Partial Transversals of Planar Regions |
| Authors: |
Keikha, Vahideh; Kerkhof, Mees van de; Kostitsyna, Irina; Kreveld, Marc van; Löffler, Maarten; Staals, Frank; Urhausen, Jérôme; Vermeulen, Jordi; Wiratma, Lionov; Geometric Computing; Sub Computational Geometry; Sub Geometric Computing; Hsu, Wen-Lian; Lee, Der-Tsai; Liao, Chung-Shou |
| Publication Year: |
2018 |
| Subject Terms: |
computational geometry; algorithms; NP-hardness; convex transversals |
| Description: |
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. |
| Document Type: |
book part |
| File Description: |
text/plain |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/373295 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/373295 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.26F5B48C |
| Database: |
BASE |