Matching Random Colored Points with Rectangles

Given n> 0 , let S⊂ [0 , 1] 2 be a set of n points, chosen uniformly at random. Let R∪ 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 axis-aligned rectangles that cover exactly two points of S of the same color, and is strong in the sense that all of its rectangles are pairwise disjoint. We prove that almost surely M(n)≥0.83n 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. © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.