000079050 001__ 79050
000079050 005__ 20230914083225.0
000079050 0248_ $$2sideral$$a111361
000079050 0247_ $$2doi$$a10.23638/DMTCS-21-3-6
000079050 037__ $$aART-2019-111361
000079050 041__ $$aeng
000079050 100__ $$aÁbrego, B.M.
000079050 245__ $$aK1,3-covering red and blue points in the plane
000079050 260__ $$c2019
000079050 5060_ $$aAccess copy available to the general public$$fUnrestricted
000079050 5203_ $$aWe say that a finite set of red and blue points in the plane in general position can be K1, 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 ¿ B can be K1, 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 ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1, 3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1, 3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1, 3-covered. (4) If b = r = 3b, then at least 9 8 (r + b- 8) points of R ¿ B can be K1, 3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1, 3-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.
000079050 536__ $$9info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT$$9This project has received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No H2020 734922-CONNECT
000079050 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/
000079050 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion
000079050 700__ $$aFernández-Merchant, S.
000079050 700__ $$aKano, M.
000079050 700__ $$aOrden, D.
000079050 700__ $$aPérez-Lantero, P.
000079050 700__ $$aSeara, C.
000079050 700__ $$0(orcid)0000-0002-9543-7170$$aTejel, J.$$uUniversidad de Zaragoza
000079050 7102_ $$12007$$2265$$aUniversidad de Zaragoza$$bDpto. Métodos Estadísticos$$cÁrea Estadís. Investig. Opera.
000079050 773__ $$g21, 3 (2019), [29 pp]$$pDiscret. math. theor. comput. sci.$$tDiscrete mathematics and theoretical computer science$$x1462-7264
000079050 85641 $$uhttps://arxiv.org/abs/1707.06856$$zTexto completo de la revista
000079050 8564_ $$s640782$$uhttps://zaguan.unizar.es/record/79050/files/texto_completo.pdf$$yVersión publicada
000079050 8564_ $$s68305$$uhttps://zaguan.unizar.es/record/79050/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada
000079050 909CO $$ooai:zaguan.unizar.es:79050$$particulos$$pdriver
000079050 951__ $$a2023-09-13-10:42:50
000079050 980__ $$aARTICLE