Convex Partial Transversals of Planar Regions
Files
Publication date
2018-12
Authors
Keikha, Vahideh
van de Kerkhof, M.A.
Kostitsyna, Irina
van Kreveld, M.J.
Löffler, Maarten
Staals, F.
Urhausen, Jérôme
Vermeulen, Jordi
Wiratma, Lionov
Editors
Hsu, Wen-Lian
Lee, Der-Tsai
Liao, Chung-Shou
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
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.
Keywords
computational geometry, algorithms, NP-hardness, convex transversals
Citation
Keikha, V, Kerkhof, M V D, Kostitsyna, I, Kreveld, M V, Löffler, M, Staals, F, Urhausen, J, Vermeulen, J & Wiratma, L 2018, Convex Partial Transversals of Planar Regions. in W-L Hsu, D-T Lee & C-S Liao (eds), Proc. 29th International Symposium on Algorithms and Computation : ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan., 52, Leibniz International Proceedings in Informatics, Dagstuhl Publishing, pp. 52:1–52:12. https://doi.org/10.4230/LIPIcs.ISAAC.2018.52