ﻻ يوجد ملخص باللغة العربية
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 $Rcup 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 $Rcup 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 $Rcup 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 $Rcup B$ in general position, with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered. (4) If $ble rle 3b$, then at least $frac{8}{9}(r+b-8)$ points of $Rcup 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.
Given a set R of red points and a set B of blue points in the plane, the Red-Blue point separation problem asks if there are at most k lines that separate R from B, that is, each cell induced by the lines of the solution is either empty or monochroma
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of th
Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$
Let $L$ be a set of $n$ lines in $R^3$ that is contained, when represented as points in the four-dimensional Plucker space of lines in $R^3$, in an irreducible variety $T$ of constant degree which is emph{non-degenerate} with respect to $L$ (see belo
It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglog n)$. This improves the previous bound of $O(log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).