Loading [MathJax]/jax/output/HTML-CSS/jax.js

Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero et al. - K1,3-covering red and blue points in the plane

dmtcs:4537 - Discrete Mathematics & Theoretical Computer Science, January 31, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-6
K1,3-covering red and blue points in the planeArticle

Authors: Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero ; Carlos Seara ; Javier Tejel

    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 RB 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 RB, 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 RB are in convex position, then at least r+b4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets RB in general position, with r=b+1, such that at most r+b5 points can be K1,3-covered. (4) If br3b, then at least 89(r+b8) points of RB can be K1,3-covered. For r>3b, there are too many red points and at least r3b of them will remain uncovered in any K1,3-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.


    Volume: Vol. 21 no. 3
    Section: Combinatorics
    Published on: January 31, 2019
    Accepted on: January 16, 2019
    Submitted on: May 25, 2018
    Keywords: Mathematics - Combinatorics,Computer Science - Computational Geometry,Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Combinatorics of Networks and Computation; Funder: European Commission; Code: 734922
    • RUI: Crossing numbers for topological drawings of the complete graph, rotation schemes, and interior triple systems; Funder: National Science Foundation; Code: 1400653

    Consultation statistics

    This page has been seen 1457 times.
    This article's PDF has been downloaded 550 times.