Matching Random Colored Points with Rectangles

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article , Conference object 01 Jan 2020 Spain, France English Publisher:Springer International PublishingJournal:Journal of Combinatorial Optimization, volume 45 (issn: 1382-6905, eissn: 1573-2886,

Copyright policy )Funded by:EC | CONNECT

Authors: Corujo, Josué; Flores-Peñaloza, David; Huemer, Clemens; Pérez-Lantero, Pablo; Seara, Carlos;

doi: 10.1007/978-3-030-39881-1_22 , 10.1007/s10878-023-01010-z

handle: 2117/180525 , 2117/406426 , 2117/367810

Matching Random Colored Points with Rectangles

- Summary
- Subjects
- Related research
  (3)
- Metrics

Abstract

Let S[0,1]2 be a set of n points, randomly and uniformly selected. Let RB 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)=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. Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640

Countries

Spain, France

Related Organizations

Paris Dauphine University
France
University of Paris
France
National Autonomous University of Mexico
Mexico
Sciences Po
France
Universitat Polite`cnica de Catalunya
Spain

View all View all

Keywords

[MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Combinatorial optimization, geometric matchings, Computational geometry, Geometria computacional, random colored points, Grafs, Random colored points, Geometric matchings, Computer graphics; computational geometry (digital and algorithmic aspects), Computational methods in Markov chains, Analysis of algorithms, :Matemàtiques i estadística::Geometria::Geometria computacional [Àrees temàtiques de la UPC], Combinatorial probability, Teoria de, Markov chains, Grafs, Teoria de, Discrete mathematics, Markov chains (discrete-time Markov processes on discrete state spaces), Graph theory, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria, Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional, Anàlisi combinatòria

3 Research products, page 1 of 1

Flips in Higher Order Delaunay Triangulations
2020IsAmongTopNSimilarDocuments
New production matrices for geometric graphs
2022IsAmongTopNSimilarDocuments
Trees whose even-degree vertices induce a path are antimagic
2020IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average