Downloads provided by UsageCounts
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.Comment: 29 pages, 10 figures, 1 table
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, :Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC], Computer science--Mathematics, star, computer science - computational geometry, Informàtica--Matemàtica, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, :68 Computer science::68R Discrete mathematics in relation to computer science [Classificació AMS], Classificació AMS::68 Computer science::68R Discrete mathematics in relation to computer science, Non-crossing geometric graph, covering, computer science - discrete mathematics, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències, red and blue points, Computer Science - Computational Geometry, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), mathematics - combinatorics, :Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC], Computer science--Mathematics, star, computer science - computational geometry, Informàtica--Matemàtica, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, :68 Computer science::68R Discrete mathematics in relation to computer science [Classificació AMS], Classificació AMS::68 Computer science::68R Discrete mathematics in relation to computer science, Non-crossing geometric graph, covering, computer science - discrete mathematics, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències, red and blue points, Computer Science - Computational Geometry, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 62 | |
| downloads | 91 |

Views provided by UsageCounts
Downloads provided by UsageCounts