Matching random colored points with rectangles

Josué Corujo (), David Flores-Peñaloza (), Clemens Huemer (), Pablo Pérez-Lantero () and Carlos Seara ()
Additional contact information
Josué Corujo: Université de Strasbourg
David Flores-Peñaloza: Universidad Nacional Autónoma de México
Clemens Huemer: Universitat Politècnica de Catalunya
Pablo Pérez-Lantero: Universidad de Santiago de Chile (USACH)
Carlos Seara: Universitat Politècnica de Catalunya

Journal of Combinatorial Optimization, 2023, vol. 45, issue 2, No 27, 18 pages

Abstract: Abstract Given $$n>0$$ n > 0 , let $$S\subset [0,1]^2$$ S ⊂ [ 0 , 1 ] 2 be a set of n points, chosen uniformly at random. Let $$R\cup B$$ 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)\ge 0.83\,n$$ 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.

Keywords: Random colored points; Geometric matchings; Markov chains; 68Q87; 68W40; 60J10; 60J22; 60C05 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01010-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:2:d:10.1007_s10878-023-01010-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01010-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().