Suppose we have $n^2$ red points and $n(n-1)$ blue points in the plane in general position. Is it possible to find a subset $S$ of red points such that the convex hull of $S$ does not contain any blue points, where $|S|>n^{\epsilon}$?
7
-
$\begingroup$ What have you tried? What theorems do you think are relevant? Have you tried any low-$n$ cases by hand to explore the idea? $\endgroup$– David G. StorkCommented Sep 18, 2018 at 22:07
-
$\begingroup$ Is this in the plane, or in $d$-dimensional space for some $d$? Obviously, $d=1$ doesn't work. $\endgroup$– Robert IsraelCommented Sep 18, 2018 at 22:16
-
1$\begingroup$ Your points had better not all (or almost all) be collinear, or there's an easy counterexample. $\endgroup$– Robert IsraelCommented Sep 18, 2018 at 22:19
-
$\begingroup$ You are right! We can assume not all of them are collinear. $\endgroup$– KenCommented Sep 18, 2018 at 22:20
-
$\begingroup$ What you are hoping for sounds very unlikely: if both the red points are uniformly distributed at random in the unit square, then taking a convex hull of $n^\epsilon$ points should give a region of area at least $n^{\epsilon-2}$. You would expect that to contain $n^\epsilon$ blue points. Even if you choose your region very carefully, I would be extremely surprised if you could avoid all of the blue points with a convex hull of that size. $\endgroup$– Anthony QuasCommented Sep 18, 2018 at 22:26
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
6
By coloring the Horton set with two colors, periodically mod 3 according to the $x$-coordinate, Devillers et al. obtained arbitrarily large bicolored point sets with no monochromatic empty convex $5$-gon (that is, monochromatic $5$-hole).
Using the fact that every set of 10 points in general position in the plane contains a $5$-hole, the bicolored Horton set has no monochromatic $10$-island (a set of 10 points of the same color such that their convex hull contains no other points of the Horton set).
So for sufficiently large $n$ the answer is no.
See http://www.eurogiga-compose.eu/posezo/horton_set for some additional references about the Horton set.
Edit: The Horton sets have size $2^m$, and the coloring by Devillers et al. has one third of the points red and two thirds blue. Take $m$ such that $2^m>3n^2$. To get $n^2$ red and $n(n-1)$ blue points, we take a second copy of the same Horton set of size $2^m$, with one third of the points blue and two thirds red, and place the two copies side by side, so that their convex hulls are disjoint. Then we cut off an appropriate number of points from the left copy ($n^2-2n$ if $n$ is divisible by $3$) and the right copy ($n^2+n$ if $n$ is divisible by $3$), by two vertical lines (or, in addition, remove a constant number of other points from the right side of the left copy or from the left side of the right copy to solve some divisibility issues). This will keep the maximum size of a monochromatic island constant (at most 19).
-
1$\begingroup$ does it contain $n^2$ and $n^2-n$ points of two colors? $\endgroup$ Commented Sep 21, 2018 at 20:23
-
$\begingroup$ good point; one color has one third of the points, the second one two thirds. I will edit the answer. $\endgroup$ Commented Sep 22, 2018 at 10:52
-
$\begingroup$ How many points do we remove in order to get prescribed number of points of both colors? $\endgroup$ Commented Sep 22, 2018 at 12:37
-
$\begingroup$ Suppose we take $3a$ rightmost points from the left copy and $3b$ leftmost points from the right copy. Then we have $a+2b$ red points and $2a+b$ blue points. This forces $3a=n^2-2n$ and $3b=n^2+n$. This has an integer solution if $n$ is divisible by $3$. I will add the numbers to the answer. $\endgroup$ Commented Sep 22, 2018 at 21:58
-
$\begingroup$ Why? Does it follow from the specific construction of Horton set? $\endgroup$ Commented Sep 22, 2018 at 22:53
$\begingroup$
$\endgroup$
Not an answer.
Consider the $n^2$ red points at the vertices of a regular $n^2$-gon, and the blue points at the vertices of an inscribed regular $n(n-1)$-gon, suitably rotated. It seems this is one of the situations that needs careful analysis.
answered Sep 18, 2018 at 22:42
$\begingroup$
$\endgroup$
Also not an answer, but an idea.
For purposes of explanation, assume no colinearity (and no parallelism, I.e. no trapezoids) in the total collection of points. It may be that colinearity will improve things, but I have not thought about that case. Pick a pair of blue points, and consider the direction perpendicular to the line connecting them.
Let's do a scan. We take a line parallel to the chosen blue edge, and run it in a scanning direction, say perpendicular to the edge. It will pass over the blue and red points, and there will be at least n pairs of red points with no blue points in between. Connect those red pairs by edges. (Or, project in the direction of the blue line to find the n pairs.)
Now pick a different pair of blue points. Repeat, and draw n or more edges. Some of the edges may be the same as before, but likely they will be different.
I think determining how many edges are produced after three or four scans in different directions will help determine epsilon. It may be that all pairs of blue points may need to be considered. In any case, one may end up with n^epsilon edges from which one might find a desired subset of red points.
Gerhard "Take A Long Linear Look" Paseman, 2018.09.18.
answered Sep 18, 2018 at 23:45