Matching Random Colored Points with Rectangles

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) \geq 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.