K1,3-covering red and blue points in the plane

Ábrego, B.M. ; Fernández-Merchant, S. ; Kano, M. ; Orden, D. ; Pérez-Lantero, P. ; Seara, C. ; Tejel, J. (Universidad de Zaragoza)

Resumen: We 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.

Idioma: Inglés

DOI: 10.23638/DMTCS-21-3-6

Año: 2019

Publicado en: Discrete mathematics and theoretical computer science 21, 3 (2019), [29 pp]
ISSN: 1462-7264

Originalmente disponible en: Texto completo de la revista

Financiación: info:eu-repo/grantAgreement/EC/H2020/734922/EU/Combinatorics of Networks and Computation/CONNECT

Tipo y forma: Article (Published version)

Área (Departamento): Área Estadís. Investig. Opera. (Dpto. Métodos Estadísticos)