# 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

Proc. 29th International Symposium on Algorithms and Computation, 2018
@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},
}