2026-04-17T03:48:05Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4064262026-01-23T03:51:37Zcom_2072_1033col_2072_452950

Matching random colored points with rectangles Corujo, Josué Flores Peñaloza, David Huemer, Clemens Pérez Lantero, Pablo Seara Ojea, Carlos Universitat Politècnica de Catalunya. Departament de Matemàtiques Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria Graph theory Discrete mathematics Random colored points Geometric matchings Markov chains Anàlisi combinatòria Grafs, Teoria de 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) 2023-03-14 Article Corujo, J. [et al.]. Matching random colored points with rectangles. "Journal of Combinatorial Optimization", 14 Març 2023, vol. 45, núm. article 81, p. 1-19. 1573-2886 https://hdl.handle.net/2117/406426 10.1007/s10878-023-01010-z eng https://link.springer.com/article/10.1007/s10878-023-01010-z info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-104129GB-I00/ES/TEORIA Y APLICACIONES DE CONFIGURACIONES DE PUNTOS Y REDES/ info:eu-repo/grantAgreement/DGR 2021-SGR-00266 Open Access 19 p. application/pdf Springer