@inproceedings{39bc6915c335433c8846689c31c965f9,

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 = "computational geometry, algorithms, NP-hardness, convex transversals",

author = "Vahideh Keikha and Kerkhof, {Mees van de} and Irina Kostitsyna and Kreveld, {Marc van} and Maarten L{\"o}ffler and Frank Staals and J{\'e}r{\^o}me Urhausen and Jordi Vermeulen and Lionov Wiratma",

year = "2018",

month = dec,

doi = "10.4230/LIPIcs.ISAAC.2018.52",

language = "English",

isbn = "978-3-95977-094-1",

series = "Leibniz International Proceedings in Informatics",

publisher = "Dagstuhl Publishing",

pages = "52:1–52:12",

editor = "Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao",

booktitle = "Proc. 29th International Symposium on Algorithms and Computation",

}