2026-08-18T12:35:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10000 2024-03-06T10:45:18Z ddc:004 open_access

Convex Partial Transversals of Planar Regions Keikha, Vahideh van de Kerkhof, Mees van Kreveld, Marc Kostitsyna, Irina Löffler, Maarten Staals, Frank Urhausen, Jérôme Vermeulen, Jordi L. Wiratma, Lionov computational geometry algorithms NP-hardness convex transversals 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vahideh Keikha and Mees van de Kerkhof and Marc van Kreveld and Irina Kostitsyna and Maarten Löffler and Frank Staals and Jérôme Urhausen and Jordi L. Vermeulen and Lionov Wiratma 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.52 urn:nbn:de:0030-drops-100003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52 eng https://creativecommons.org/licenses/by/3.0/legalcode