Convex Partial Transversals of Planar Regions

Abstract

We consider the problem of testing, for a given set of planar regions \(\cal R\) and an integer \(k\), whether there exists a set of \(k\) points in convex position such that each of the \(k\) points is contained in a unique region. We show that this problem is NP-hard in general, even when the regions are 3-oriented line segments or disjoint. On the other hand, we provide a polynomial time algorithm for the case where the regions are vertical line segments.

Corresponding Publications

Convex Partial Transversals of Planar Regions

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

Proc. 29th International Symposium on Algorithms and Computation, 2018

Download Local Copy View Slides Export Citation 
@incollection{convex_kgon2018,
  author = {Keikha, Vahideh and van der Kerkhof, Mees and van Kreveld, Marc and
                 Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank
                 and Urhausen, J{\'e}r{\^o}me and Vermeulen, Jordi L.
                 and Wiratma, Lionov},
  title = {Convex Partial Transversals of Planar Regions},
  booktitle = {Proc. 29th International Symposium on Algorithms and Computation},
  year = {2018},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Yilan, Taiwan},
  numpages = {12},
  category = {other},
  volume = {123},
  url = {http://drops.dagstuhl.de/opus/volltexte/2018/10000},
  doi = {10.4230/LIPIcs.ISAAC.2018.52},
}