Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero et al. - $K_{1,3}$-covering red and blue points in the plane

dmtcs:4537 - Discrete Mathematics & Theoretical Computer Science, January 31, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-6
$K_{1,3}$-covering red and blue points in the plane

Authors: Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero ; Carlos Seara ; Javier Tejel

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.

Volume: Vol. 21 no. 3
Section: Combinatorics
Published on: January 31, 2019
Accepted on: January 31, 2019
Submitted on: May 25, 2018
Keywords: Mathematics - Combinatorics,Computer Science - Computational Geometry,Computer Science - Discrete Mathematics