Coloring Points with Respect to Squares | Discrete & Computational Geometry Skip to main content
Springer Nature Link
Log in

Coloring Points with Respect to Squares

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set of points in the plane \({\mathcal {S}} \subset {\mathbb {R}}^2\) can be 2-colored such that every axis-parallel square that contains at least m points from \({\mathcal {S}}\) contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering 2-coloring points with respect to homothets of a fixed parallelogram.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Notes

  1. In a multisubfamily we allow taking multiple copies of the same set.

  2. In fact in early papers that considered only coverings by translates, all mentioned variants of cover-decomposability were defined for sets instead of families, where a set is cover-decomposable if the family of its translates is cover-decomposable in the way we define it in this paper.

  3. An octant is the set of points \(\{(x,y,z): x<a,y<b,z<c\}\) in the space for some a, b and c.

  4. Unless stated otherwise, logarithms in this paper are base 2.

  5. In a family of pseudo-disks the boundaries of every two regions cross at most twice.

References

  1. Ackerman, E., Pinchasi, R.: On coloring points with respect to rectangles. J. Combin. Theory Ser. A 120(4), 811–815 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  2. Ajwani, D., Elbassioni, K., Govindarajan, S., Ray, S.: Conflict-free coloring for rectangle ranges using \(O(n^{.382})\) colors. Discrete Comput. Geom. 48(1), 39–52 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  3. Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., Ramos, P.: Decomposition of multiple coverings into more parts. Discrete Comput. Geom. 44(3), 706–723 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bose, P., Carmi, P., Collette, S., Smid, M.: On the stretch factor of convex Delaunay graphs. J. Comput. Geom. 1(1), 41–56 (2010)

    MATH  MathSciNet  Google Scholar 

  5. Buzaglo, S., Pinchasi, R., Rote, G.: Topological hypergraphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 71–81. Springer, New York (2013)

    Chapter  Google Scholar 

  6. Cardinal, J., Knauer, K., Micek, P., Ueckerdt, T.: Making triangles colorful. J. Comput. Geom. 4(1), 240–246 (2013)

    MATH  MathSciNet  Google Scholar 

  7. Cardinal, J., Knauer, K., Micek, P., Ueckerdt, T.: Making octants colorful and related covering decomposition problems. SIAM J. Discrete Math. 28(4), 1948–1959 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  8. Chan, T.M.: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In: Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG’12), pp. 293–302. ACM, New York (2012)

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

    Article  MATH  MathSciNet  Google Scholar 

  10. Gibson, M., Varadarajan, K.: Optimally decomposing coverings with translates of a convex polygon. Discrete Comput. Geom. 46(2), 313–333 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  11. Har-Peled, S., Smorodinsky, Sh.: Conflict-free coloring of points and simple regions in the plane. Discrete Comput. Geom. 34(1), 47–70 (2005)

  12. Keszegh, B.: Weak conflict-free colorings of point sets and simple regions. In: Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG’07), pp. 97–100 (2007)

  13. Keszegh, B.: Coloring half-planes and bottomless rectangles. Comput. Geom. 45(9), 495–507 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  14. Keszegh, B., Pálvölgyi, D.: Octants are cover-decomposable. Discrete Comput. Geom. 47(3), 598–609 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  15. Keszegh, B., Pálvölgyi, D.: Convex polygons are self-coverable. Discrete Comput. Geom. 51(4), 885–895 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  16. Keszegh, B., Pálvölgyi, D.: Octants are cover-decomposable into many coverings. Comput. Geom. 47(5), 585–588 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  17. Keszegh, B., Pálvölgyi, D.: More on decomposing coverings by octants. J. Comput. Geom. 6(1), 300–315 (2015)

    MATH  MathSciNet  Google Scholar 

  18. Keszegh, B., Pálvölgyi, D.: Proper coloring of geometric hypergraphs. In: Symposium on Computational Geometry 2017 (SoCG’17). arXiv:1612.02158

  19. Klein, R.: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science, vol. 400. Springer, Berlin (1989)

  20. Kovács, I.: Indecomposable coverings with homothetic polygons. Discrete Comput. Geom. 53(4), 817–824 (2015)

    Article  MATH  MathSciNet  Google Scholar 

  21. Ma, L.: Bisectors and Voronoi diagrams for convex distance functions. PhD Thesis, FernUniversität Hagen, Hagen (2000). http://www.fernuni.de/ks/download/pub/tr267.pdf

  22. Pach, J.: Decomposition of multiple packing and covering. 2. Kolloquium über Diskrete Geometrie, pp. 169–178. Institut für Mathematik der Universität Salzburg, Salzburg (1980)

  23. Pach, J.: Covering the plane with convex polygons. Discrete Comput. Geom. 1(1), 73–81 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  24. Pach, J., Pálvölgyi, D.: Unsplittable coverings in the plane. Adv. Math. 302, 433–457 (2016)

    Article  MATH  MathSciNet  Google Scholar 

  25. Pach, J., Pálvölgyi, D., Tóth, G.: Survey on decomposition of multiple coverings. In: Bárány, I., et al. (eds.) Geometry—Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol. 24, pp. 219–257. Springer, Berlin (2013)

    Google Scholar 

  26. Pach, J., Tardos, G.: Coloring axis-parallel rectangles. J. Combin. Theory Ser. A 117(6), 776–782 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  27. Pach, J., Tardos, G., Tóth, G.: Indecomposable coverings. In: Akiyama, J., et al. (eds.) Discrete Geometry, Combinatorics and Graph Theory. Lecture Notes in Computer Sciences, vol. 4381, pp. 135–148. Springer, Berlin (2007)

  28. Pach, J., Tardos, G., Tóth, G.: Indecomposable coverings. Can. Math. Bull. 52(3), 451–463 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  29. Pach, J., Tóth, G.: Conflict-free colorings. In: Aronov, B., et al. (eds.) Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 665–671. Springer, Berlin (2003)

    Chapter  Google Scholar 

  30. Pach, J., Tóth, G.: Decomposition of multiple coverings into many parts. Comput. Geom. 42(2), 127–133 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  31. Pálvölgyi, D.: Indecomposable coverings with concave polygons. Discrete Comput. Geom. 44(3), 577–588 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  32. Pálvölgyi, D.: Cover decomposition page. http://www.cs.elte.hu/~dom/covdec

  33. Pálvölgyi, D., Tóth, G.: Convex polygons are cover-decomposable. Discrete Comput. Geom. 43(3), 483–496 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  34. Sarıöz, D.: Generalized Delaunay graphs with respect to any convex set are plane graphs (2010). arXiv:1012.4881

  35. Smorodinsky, Sh.: Conflict-free coloring and its applications. In: Bárány, I. (ed.) Geometry—Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, vol. 24, pp. 331–389. Springer, Berlin (2013)

  36. Smorodinsky, Sh., Yuditsky, Y.: Polychromatic coloring for half-planes. J. Combin. Theory Ser. A 119(1), 146–154 (2012)

  37. Tardos, G., Tóth, G.: Multiple coverings of the plane with triangles. Discrete Comput. Geom. 38(2), 443–450 (2007)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgements

E. Ackerman’s research partially supported by ERC Advanced Research Grant No. 267165 (DISCONV). B. Keszegh’s research supported by the National Research, Development and Innovation Office – NKFIH under the Grant PD 108406 and K 116769 and by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences. M. Vizer’s research supported by the National Research, Development and Innovation Office – NKFIH under the Grant SNN 116095. We thank the reviewers for reading our paper and for their valuable remarks. In particular, suggestions of one of reviewers helped to simplify some basic lemmas and improve the constant in our main theorem.

Author information

Authors and Affiliations

  1. Department of Mathematics, Physics, and Computer Science, University of Haifa at Oranim, Tivon, 36006, Israel

    Eyal Ackerman

  2. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, 1053, Hungary

    Balázs Keszegh & Mate Vizer

Authors
  1. Eyal Ackerman
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Balázs Keszegh
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Mate Vizer
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Balázs Keszegh.

Additional information

Editor in Charge: János Pach

A preliminary version of this paper was presented at the 32nd International Symposium on Computational Geometry (SoCG 2016).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ackerman, E., Keszegh, B. & Vizer, M. Coloring Points with Respect to Squares. Discrete Comput Geom 58, 757–784 (2017). https://doi.org/10.1007/s00454-017-9902-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-017-9902-y

Keywords

Mathematics Subject Classification