@inproceedings{426f3c24f9cd46dd819f8d5102bef300,
title = "Convex partial transversals of planar regions",
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 = "Algorithms, Computational geometry, Convex transversals, NP-hardness",
author = "Vahideh Keikha and {van de Kerkhof}, Mees and {van Kreveld}, Marc and Irina Kostitsyna and Maarten L{\"o}ffler and Frank Staals and J{\'e}r{\^o}me Urhausen and Vermeulen, {Jordi L.} and Lionov Wiratma",
year = "2018",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2018.52",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao",
booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",
note = "29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",
}