Back to Search Start Over

$K_{1,3}$-covering red and blue points in the plane

Authors :
Ábrego, Bernardo M.
Fernández-Merchant, Silvia
Kano, Mikio
Orden, David
Pérez-Lantero, Pablo
Seara, Carlos
Tejel, Javier
Source :
Discrete Mathematics & Theoretical Computer Science, Vol. 21 no. 3 , Combinatorics (January 31, 2019) dmtcs:4537
Publication Year :
2017

Abstract

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.<br />Comment: 29 pages, 10 figures, 1 table

Details

Database :
arXiv
Journal :
Discrete Mathematics & Theoretical Computer Science, Vol. 21 no. 3 , Combinatorics (January 31, 2019) dmtcs:4537
Publication Type :
Report
Accession number :
edsarx.1707.06856
Document Type :
Working Paper
Full Text :
https://doi.org/10.23638/DMTCS-21-3-6