[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Matching random colored points with rectangles

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data avalibility statement

sharing not applicable to this article as no datasets were generated or analyzed during the current study.

References

  • Ábrego BM, Arkin EM, Fernández-Merchant S, Hurtado F, Kano M, Mitchell JSB, Urrutia J (2009) Matching points with squares. Discrete Comput Geom 41(1):77–95

    Article  MathSciNet  MATH  Google Scholar 

  • Arizmendi O, Salazar G (2016) Large area convex holes in random point sets. SIAM J Discrete Math 30(3):1866–1875

    Article  MathSciNet  MATH  Google Scholar 

  • Asgeirsson E, Stein C (2006) Using Markov chains to design algorithms for bounded-space on-line bin cover. In: Proceedings of the workshop on algorithm engineering and experiments (ALENEX), pp 75–85

  • Balko M, Scheucher M, Valtr P (2020) Holes and islands in random point sets. https://doi.org/10.1002/rsa.21037. arXiv:2003.00909

  • Balogh J, González-Aguilar H, Salazar G (2013) Large convex holes in random point sets. Comput Geom 46(6):725–733

    Article  MathSciNet  MATH  Google Scholar 

  • Bereg S, Mutsanas N, Wolff A (2009) Matching points with rectangles and squares. Comput Geom 42(2):93–108

    Article  MathSciNet  MATH  Google Scholar 

  • Caraballo LE, Ochoa C, Pérez-Lantero P, Rojas-Ledesma J (2017) Matching colored points with rectangles. J Comb Optim 33(2):403–421

    Article  MathSciNet  MATH  Google Scholar 

  • Chen X, Pach J, Szegedy M, Tardos G (2009) Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct Algorithms 34(1):11–23

    Article  MathSciNet  MATH  Google Scholar 

  • Coffman Jr EG, Johnson DS, Shor PW, Weber RR (1993) Markov chains, computer proofs, and average-case analysis of best fit bin packing. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp 412–421

  • Corujo J, Flores-Peñaloza D, Huemer C, Pérez-Lantero P, Seara C (2020) Matching random colored points with rectangles. In: International workshop on algorithms and computation. Springer, pp 261–272

  • Devillers O, Duchon P, Glisse M, Goaoc X (2018) On order types of random point sets. arXiv:1812.08525

  • Doerr B (2014) A lower bound for the discrepancy of a random point set. J Complex 30(1):16–20

    Article  MathSciNet  MATH  Google Scholar 

  • Dumitrescu A, Kaye R (2001) Matching colored points in the plane: some new results. Comput Geom 19(1):69–85

    Article  MathSciNet  MATH  Google Scholar 

  • Dumitrescu A, Steiger W (2000) On a matching problem in the plane. Discrete Math 211(1–3):183–195

    Article  MathSciNet  MATH  Google Scholar 

  • Fabila-Monroy R, Huemer C (2017) Order types of random point sets can be realized with small integer coordinates. In: XVII Spanish meeting on computational geometry: book of abstracts, Alicante, June 26–28, pp 73–76

  • Fabila-Monroy R, Huemer C, Mitsche D (2015) Empty non-convex and convex four-gons in random point sets. Stud Sci Math Hung 52(1):52–64

    MathSciNet  MATH  Google Scholar 

  • Kenyon C, Rabani Y, Sinclair A (1998) Biased random walks, Lyapunov functions, and stochastic analysis of Best Fit bin packing. J Algorithms 27(2):218–235

    Article  MathSciNet  MATH  Google Scholar 

  • Larson LC (1983) Problem-Solving Through Problems. Problem Books in Mathematics. Springer, New York

    Book  Google Scholar 

  • Norris JR (1998) Markov chains. In: Cambridge series in statistical and probabilistic mathematics, vol 2. Cambridge University Press, Cambridge. Reprint of 1997 original

Download references

Acknowledgements

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.

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922.

Author information

Authors and Affiliations

  1. Institut de Recherche Mathématique Avancée (IRMA), Université de Strasbourg, Strasbourg, France

    Josué Corujo

  2. Departamento de Matemáticas, Facultad de Ciencias, Universidad Nacional Autónoma de México, Mexico City, Mexico

    David Flores-Peñaloza

  3. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain

    Clemens Huemer & Carlos Seara

  4. Departamento de Matemática y Ciencia de la Computación, Facultad de Ciencia, Universidad de Santiago de Chile (USACH), Santiago, Chile

    Pablo Pérez-Lantero

Authors
  1. Josué Corujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Flores-Peñaloza
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Clemens Huemer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pablo Pérez-Lantero
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Carlos Seara
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed equally to the results of this manuscript. They also read and approved this final version.

Corresponding author

Correspondence to Pablo Pérez-Lantero.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this work appeared in WALCOM 2020, 14th International Conference and Workshop on Algorithms and Computation, Singapore (Corujo et al. 2020).

Bichromatic matching

Bichromatic matching

In this section, we present our results when matching red points with blue points. The Markov chain for this case consists of 20 states \(\{e_1,e_2,\ldots ,e_{20}\}\), and it is described in Fig. 9. Its transition matrix is showed in Fig. 8.

We have that \(f(e)=2\) for all \(e\in \{e_3,e_7,e_9,e_{10},e_{12},e_{17},e_{18},e_{19},e_{20}\}\), \(f(e_{11})=4\), and \(f(e)=0\) for every other state e. Furthermore, the stationary distribution \(s=(s_1,\ldots ,s_{20})\) satisfies

$$\begin{aligned}{} & {} s_3 ~=~ \frac{4694}{26397},~ s_7 ~=~ \frac{2560}{26397},~ s_9 ~=~ \frac{340}{26397},~ s_{10} ~=~ \frac{85}{2933},~ s_{11} ~=~ \frac{85}{8799}\\{} & {} s_{12} ~=~ \frac{340}{26397},~ s_{17} ~=~ \frac{340}{26397},~ s_{18} ~=~ \frac{68}{26397},~ s_{19} ~=~ \frac{68}{26397},~ s_{20} ~=~ \frac{68}{26397}. \end{aligned}$$

Then, we obtain

$$\begin{aligned} \alpha _3 ~{} & {} =~ 2(s_3+s_7+s_9+s_{10}+s_{17}+s_{18}+s_{19}+s_{20}) + 4s_{11} ~\nonumber \\{} & {} =~ \frac{19506}{26397} ~\approx ~ 0.738947608. \end{aligned}$$

By Theorem 1, taking \(\varepsilon =\alpha _3-0.7389>0\), for n large enough we have almost surely that at least \(0.7389\,n\) points can be matched (Fig. 9).

Fig. 8
figure 8

The transition matrix of the Markov chain for \(k=3\), when matching red points with blue points (Color figure online)

Full size image
Fig. 9
figure 9

The table shows the 20 states of the Markov chain for \(k=3\), when matching red points with blue points. In the second column we show the first component of \(e_i\), and in the third column we show \(f(e_i)\). In the last column we show the neighborhood of \(e_i\) as pairs \((e_j,P_{i,j})\), where \(P_{i,j}\) is the transition probability from \(e_i\) to \(e_j\) (Color figure online)

Full size image

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Corujo, J., Flores-Peñaloza, D., Huemer, C. et al. Matching random colored points with rectangles. J Comb Optim 45, 81 (2023). https://doi.org/10.1007/s10878-023-01010-z

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10878-023-01010-z

Keywords

Mathematics Subject Classification

Search

Navigation