Matching Random Colored Points with Rectangles

Let S ⊂ [0, 1]2 be a set of n points, randomly and uniformly selected. 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 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) ≥ 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. © Springer Nature Switzerland AG 2020.