Convex Partial Transversals of Planar Regions

Vahideh Keikha, Mees van de Kerkhof, Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi Vermeulen, Lionov Wiratma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.
Original languageEnglish
Title of host publicationProc. 29th International Symposium on Algorithms and Computation
Subtitle of host publicationISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan
EditorsWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
PublisherDagstuhl Publishing
ISBN (Print)978-3-95977-094-1
Publication statusPublished - Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics
ISSN (Electronic)1868-8969


  • computational geometry
  • algorithms
  • NP-hardness
  • convex transversals


Dive into the research topics of 'Convex Partial Transversals of Planar Regions'. Together they form a unique fingerprint.

Cite this