Matching random colored points with rectangles

Abstract

The version of record of this article, first published in Journal of Combinatorial Optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10878-023-01010-z

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.

Author Corujo was supported by grants from the Université Paris-Dauphine (France) and the ITI IRMIA++. Author Flores-Peñaloza was supported by project PAPIIT IN120520 (UNAM, Mexico). Author Huemer was supported by projects PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2021-SGR-00266. Author Pérez-Lantero was supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Author Seara was supported by project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/ 501100011033 and Gen. Cat. DGR 2021-SGR-00266.

Postprint (author's final draft)