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