Advertisement
Published in:
2020 | OriginalPaper | Chapter
Matching Random Colored Points with Rectangles
Authors : Josué Corujo, David Flores-Peñaloza, Clemens Huemer, Pablo Pérez-Lantero, Carlos Seara
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \(S\subset [0,1]^2\) be a set of n points, randomly and uniformly selected. Let \(R\cup B\) be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely \(M(n)\ge 0.83\,n\) for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain.