Convex partial transversals of planar regions

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

Research output: Contribution to journalArticleAcademic

Abstract

We consider the problem of testing, for a given set of planar regions $\cal R$ and an integer $k$, whether there exists a convex shape whose boundary intersects at least $k$ regions of $\cal R$. We provide a polynomial time algorithm for the case where the regions are 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
Article number1809.10078v1
Number of pages29
JournalarXiv
Publication statusPublished - 26 Sep 2018

Keywords

  • cs.CG

Fingerprint Dive into the research topics of 'Convex partial transversals of planar regions'. Together they form a unique fingerprint.

Cite this