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.
@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.}, }