Matching colored points with rectangles

DOI10.1007/S10878-015-9971-XMaRDI QIDQ511687zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 22 February 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.3696

zbMATH Keywords

computational geometryapproximationsmaximum independent setrectanglesmatching colored points

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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 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. In this paper 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 $mathsfNP$-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 $mathsfNP$-hard, even if $S$ is in general position. These $mathsfNP$-hardness results follow by showing that deciding the existence of a perfect matching is $mathsfNP$-complete in each case. The approximation results are based on a relation of our problem with the problem of finding a maximum independent set in a family of axis-aligned rectangles. With this paper we extend previous ones on matching one-colored points with rectangles and squares, and matching two-colored points with segments. Furthermore, using our techniques, we prove that it is $mathsfNP$-complete to decide a perfect matching with rectangles in the case where all points have the same color, solving an open problem of Bereg, Mutsanas, and Wolff [CGTA (2009)].

Recommendations

• Matching points with rectangles and squares
• Matching colored points in the plane: Some new results
• A matching problem in the plane
• SOFSEM 2006: Theory and Practice of Computer Science
• Matching random colored points with rectangles

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• A note on maximum independent sets in rectangle intersection graphs
• Admission control in networks with advance reservations
• Approximation algorithms for maximum independent set of pseudo-disks
• Coloring and maximum independent set of rectangles
• Covering points by disjoint boxes with outliers
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Independent set of intersection graphs of convex objects in 2D
• Jump number of two-directional orthogonal ray graphs
• Label placement by maximum independent set in rectangles
• Matching colored points in the plane: Some new results
• Matching points with rectangles and squares
• Matching points with squares
• Maximum independent set of rectangles
• Minimum-weight triangulation is NP-hard
• On a matching problem in the plane
• On rectangle intersection and overlap graphs
• Optimal packing and covering in the plane are NP-complete
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Problem-solving through problems.
• Removing degeneracies by perturbing the problem or perturbing the world
• The Problem of Compatible Representatives

Cited in

(17)

• Matching points with squares
• Maximum box problem on stochastic points
• On maximum-sum matchings of points
• $K_{1,3}$-covering red and blue points in the plane
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• SOFSEM 2006: Theory and Practice of Computer Science
• Connecting colored point sets
• On some matching problems under the color-spanning model
• Matching points with disks with a common intersection
• Applications of a numbering scheme for polygonal obstacles in the plane
• Matching random colored points with rectangles
• Matching fixed rectangles in 2-dimension
• Labeling points with given rectangles
• Matching Points with Circles and Squares
• Matching colored points in the plane: Some new results
• Matching points with rectangles and squares
• Computing the coarseness with strips or boxes

This page was built for publication: Matching colored points with rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511687)