Matching random colored points with rectangles

Abstract

Given $n>0$, let $S\subset [0,1]^2$ be a set of $n$ points, chosen uniformly at random. 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 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)\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.