On Polygons Excluding Point Sets

Details On Polygons Excluding Point Sets On Polygons Excluding Point Sets

2009-12-15

arxiv.org/abs/0912.2914v1

Mathematics

Combinatorics

14 pages, 15 figures

Scientific paper

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 $B\cup R$ 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 polynomial in $l$, such that one can always find a blue polygonization excluding all red points, whenever $k\geq K$. Some other related problems are also considered.

Affiliated with

Also associated with

No associations

Rating

On Polygons Excluding Point Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Polygons Excluding Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Polygons Excluding Point Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-305740