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: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
9 Downloads (Pure)

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.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Place of PublicationWadern
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)9783959770941
DOIs
Publication statusPublished - 1 Dec 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan
Duration: 16 Dec 201819 Dec 2018

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period16/12/1819/12/18

Keywords

  • Algorithms
  • Computational geometry
  • Convex transversals
  • NP-hardness

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

Cite this