$K_{1,3}$-covering red and blue points in the plane
2019
We say that a finite set of red and blue points in the plane in general
position can be $K_{1,3}$-covered if the set can be partitioned into subsets of
size $4$, with $3$ points of one color and $1$ point of the other color, in
such a way that, if at each subset the fourth point is connected by
straight-line segments to the same-colored points, then the resulting set of
all segments has no crossings. We consider the following problem: Given a set
$R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general
position, how many points of $R\cup B$ can be $K_{1,3}$-covered? and we prove
the following results:
(1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$,
then there are point sets $R\cup B$, like $\{1,3\}$-equitable sets (i.e.,
$r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered.
(2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position,
then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight.
(3) There are arbitrarily large point sets $R\cup B$ in general position,
with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered.
(4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b-8)$ points of $R\cup B$
can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and at
least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
3
Citations
NaN
KQI