On Polygons Excluding Point Sets

By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that is in general position, and the convex hull of B contains k interior blue points and l interior red points. Hurtado et al. found sufficient conditions for the existence of a blue polygonization that encloses all red points. We consider the dual question of the existence of a blue polygonization that excludes all red points R. We show that there is a minimal number K = K(l), which is bounded from above by a polynomial in l, such that one can always find a blue polygonization excluding all red points, whenever k a parts per thousand yen K. Some other related problems are also considered.


Published in:
Graphs And Combinatorics, 29, 6, 1741-1753
Year:
2013
Publisher:
Tokyo, Springer Japan Kk
ISSN:
0911-0119
Keywords:
Laboratories:




 Record created 2013-12-09, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)