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
    To Appear.
    @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 L. Vermeulen, Jordi 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},
      note = {To Appear.},
    }