Matching colored points with rectangles

L. E. Caraballo (), C. Ochoa (), P. Pérez-Lantero () and J. Rojas-Ledesma ()
Additional contact information
L. E. Caraballo: Universidad de Sevilla
C. Ochoa: Universidad de Chile
P. Pérez-Lantero: Universidad de Valparaíso
J. Rojas-Ledesma: Universidad de Chile

Journal of Combinatorial Optimization, 2017, vol. 33, issue 2, No 4, 403-421

Abstract: Abstract Let S be a point set in the plane such that each of its elements is colored either red or blue. A matching of S with rectangles is any set of pairwise-disjoint axis-aligned closed rectangles such that each rectangle contains exactly two points of S. Such a matching is monochromatic if every rectangle contains points of the same color, and is bichromatic if every rectangle contains points of different colors. We study the following two problems: (1) Find a maximum monochromatic matching of S with rectangles. (2) Find a maximum bichromatic matching of S with rectangles. For each problem we provide a polynomial-time approximation algorithm that constructs a matching with at least 1 / 4 of the number of rectangles of an optimal matching. We show that the first problem is $$\mathsf {NP}$$ NP -hard even if either the matching rectangles are restricted to axis-aligned segments or S is in general position, that is, no two points of S share the same x or y coordinate. We further show that the second problem is also $$\mathsf {NP}$$ NP -hard, even if S is in general position. These $$\mathsf {NP}$$ NP -hardness results follow by showing that deciding the existence of a matching that covers all points is $$\mathsf {NP}$$ NP -complete in each case. Additionally, we prove that it is $$\mathsf {NP}$$ NP -complete to decide the existence of a matching with rectangles that cover all points in the case where all the points have the same color, solving an open problem of Bereg et al. (Comput Geom 42(2):93–108, 2009).

Keywords: Computational geometry; Matching colored points; Maximum independent set; Rectangles; Approximations (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9971-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-015-9971-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9971-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().