Matching colored points with rectangles

DOI10.1007/S10878-015-9971-XzbMATH Open1361.90049arXiv1309.3696OpenAlexW1530429524MaRDI QIDQ511687FDOQ511687

Sumit K. Garg, Yong-Cai Geng

Publication date: 22 February 2017

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

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)].

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

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

zbMATH Keywords

computational geometryapproximationsmaximum independent setrectanglesmatching colored points

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Minimum-weight triangulation is NP-hard
• The Problem of Compatible Representatives
• Independent set of intersection graphs of convex objects in 2D
• Optimal packing and covering in the plane are NP-complete
• Coloring and Maximum Independent Set of Rectangles
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Title not available (Why is that?)
• Jump Number of Two-Directional Orthogonal Ray Graphs
• Title not available (Why is that?)
• Polynomial-time approximation schemes for packing and piercing fat objects
• Matching points with squares
• Label placement by maximum independent set in rectangles
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Title not available (Why is that?)
• A note on maximum independent sets in rectangle intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Problem-solving through problems.
• Admission control in networks with advance reservations
• On a matching problem in the plane
• Removing degeneracies by perturbing the problem or perturbing the world
• On rectangle intersection and overlap graphs
• Matching colored points in the plane: Some new results
• Covering points by disjoint boxes with outliers
• Matching points with rectangles and squares

Cited In (14)

• Matching points with squares
• Maximum box problem on stochastic points
• On maximum-sum matchings of points
• Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity
• Connecting colored point sets
• 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
• Complexity results on untangling red-blue matchings
• 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
• 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)