Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Almost Empty Monochromatic Triangles and Convex Quadrilaterals in Colored Point Sets

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let S be a set of N points on the plane in general position, colored arbitrarily with c colors (\(c\in {\mathbb {N}}\)). A subset of points is said to be monochromatic if all its points have the same color. In this paper we show that if N is sufficiently large, then S contains a monochromatic triangle with vertices in S and containing at most \(c-3\) points in its interior \((c \ge 4)\). The particular case \(c=4\) solves the conjecture of Basu, Bhattacharya, and Das in [6]. For the case of two colors, it is still unknown whether every sufficiently large bichromatic point set contains an empty monochromatic convex quadrilateral [11]. In this direction we show that if S is sufficiently large, then it always contains a convex monochromatic quadrilateral with at most \(2c-3\) points in its interior \((c \ge 2)\). We also show a general result on the number of empty convex quadrilaterals with disjoint interiors. Let P be a set of n points in general position. It is straightforward to see that if the elements of P are the vertices of a convex polygon, \(n \ge 4\), P always has \(\left\lceil \frac{n-3}{2} \right\rceil \) empty convex quadrilaterals with disjoint interiors. In this paper we prove that any point set P in general position has at least \(\left\lfloor \frac{n-3}{2}\right\rfloor \) interior disjoint empty convex quadrilaterals. We also give direct consequences of this theorem related to simultaneously flippable edges in triangulations and convex decompositions of point sets. We show that for any point set P there is always a triangulation that has \(\left\lfloor \frac{n-3}{2}\right\rfloor \) simultaneously flippable edges. We also show that there is always a convex decomposition of P consisting of triangles and convex quadrilaterals with at most \({3n-2h\over 2}\) elements, where h is the number of points in the convex hull of P.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

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

Similar content being viewed by others

References

  1. Aichholzer, O., Fabila-Monroy, R., Flores-Peñaloza, D., Hackl, T., Huemer, C., Urrutia, J.: Empty monochromatic triangles. Comput. Geom. Theory Appl. 42, 934–938 (2009)

    Article  MathSciNet  Google Scholar 

  2. Aichholzer, O., Fabila-Monroy, R., Gonzalez-Aguilar, H., Hackl, T., Heredia, M.A., Huemer, C., Urrutia, J., Valtr, P., Vogtenhuber, B.: On \(k\)-gons and \(k\)-holes in point sets. Comput. Geom. Theory Appl. 48(7), 528–537 (2015)

    Article  MathSciNet  Google Scholar 

  3. Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Vogtenhuber, B.: Large bichromatic point sets admit empty monochromatic 4-gons. SIAM J. Discret. Math. 23(4), 2147–2155 (2010)

    Article  MathSciNet  Google Scholar 

  4. Aichholzer, O., Hackl, T., Hoffmann, M., Pilz, A., Rote, G., Speckmann, B., Vogtenhuber, B.: Plane graphs with parity constraints, Proceedings Algorithms And Data Structures Symposium (WADS), LNCS 5664, pp. 13-24 (2009)

    Google Scholar 

  5. Aichholzer, O., Krasser, H.: The point set order type data base: A collection of applications and results, In Proceedings 13th Annual Canadian Conference on Computational Geometry CCCG 2001, pp. 17-20, Waterloo, Ontario, Canada (2001)

  6. Basu, D., Bhattacharya, B., Das, S.: Almost empty monochromatic triangles in planar point sets. Electron. Notes Discret. Math. 44, 53–59 (2013)

    Article  Google Scholar 

  7. Bose, P., Czyzowicz, J., Gao, Z., Morin, P., Wood, D.: Simultaneous diagonal flips in plane triangulations, In Proceedings of 17th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’06), pp. 212-221 (2006)

  8. Bose, P., Toussaint, G.T.: Characterizing and efficiently computing quadrangulations of planar point sets. Comput. Aided Geom. Design 14, 763–785 (1997)

    Article  MathSciNet  Google Scholar 

  9. Cano, J., García, A., Hurtado, F., Sakai, T., Tejel, J., Urrutia, J.: Blocking the k-holes of point sets in the plane, Graphs and Combinatorics, pp. 1-17 (2014)

  10. Czyzowicz, J., Kranakis, E., Urrutia, J.: Guarding the convex subsets of a point set, 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, pp. 47-50, (August 16–19th 2000)

  11. Devillers, O., Hurtado, F., Károlyi, G., Seara, C.: Chromatics variants of the Erdös-Szekeres theorem on points in convex position. Comput. Geom. 26, 193–208 (2003)

    Article  MathSciNet  Google Scholar 

  12. Erdös, P.: Some more problems on elementary geometry. Aust. Math. Soc. Gaz. 5, 52–54 (1978)

    MathSciNet  MATH  Google Scholar 

  13. Erdös, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)

    MathSciNet  MATH  Google Scholar 

  14. Erdös, P., Szekeres, G.: On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest, Eötvös, Sect. Math. Vol. 3-4, pp.53-62, (1960-61)

  15. Fevens, T., Meijer, H., Rappaport, D.: Minimum convex partition of a constrained point set. Discret. Appl. Math. 109, 95–107 (2001)

    Article  MathSciNet  Google Scholar 

  16. Galtier, J., Hurtado, F., Noy, M., Perennes, S., Urrutia, J.: Simultaneous edge flipping in triangulations, International Journal of. Comput. Geom. 13(2), 113–133 (2004)

    MATH  Google Scholar 

  17. García-López, J., Nicolás, C.: Planar point sets with large minimum convex partitions, 22nd European Workshop on Computational Geometry, pp. 51–54. Delphi, Greece (2006)

    Google Scholar 

  18. Gerken, T.: Empty convex hexagons in planar point sets. Discret. Comput. Geom. 39, 239–272 (2008)

    Article  MathSciNet  Google Scholar 

  19. Harborth, H.: Konvexe funfecke in ebenen punktmengen. Elemente der Mathematik 33(5), 116–118 (1978)

    MathSciNet  MATH  Google Scholar 

  20. Horton, J.D.: Sets with no empty convex 7-gons. Can. Math. Bull. 26, 482–484 (1983)

    Article  MathSciNet  Google Scholar 

  21. Hosono, K.: On convex decompositions of a planar point set. Discret. Math. 309(6), 1714–1717 (2009)

    Article  MathSciNet  Google Scholar 

  22. Huemer, C., Seara, C.: 36 Two-colored points with no empty monochromatic convex fourgons, Geombinatorics, Vol. XIX(1), pp. 5-6 (2009)

  23. Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations, Discrete and Computational Geoemetry, Vol. 22, pp. 333-346, (1999). Also in Proceedings of 12 ACM Symposium on Computational Geometry, pp. 214-223, (May 24-26 1996)

    Article  MathSciNet  Google Scholar 

  24. Kalbfleisch, J., Stanton, R.: A combinatorial problem on convex n-gons, In Proc. Louisiana Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, pp. 180-188 (1970)

  25. Katchalski, M., Meir, A.: On empty triangles determined by points in the plane. Acta Mathematica Hungarica 51(3–4), 323–328 (1998)

    MathSciNet  MATH  Google Scholar 

  26. Neumann, V., Rivera-Campo, E., Urrutia, J.: A note on convex decompositions. Graphs Comb. 20(2), 223–231 (2004)

    Article  Google Scholar 

  27. Nicolás, C.M.: The empty hexagon theorem. Discret. Comput. Geom. 38, 389–397 (2007)

    Article  MathSciNet  Google Scholar 

  28. Nyklová, H.: Almost empty polygons. Studia Scientiarum Mathematicarum Hungarica 38, 269–286 (2003)

    Article  MathSciNet  Google Scholar 

  29. Pach, J., Tóth, G.: Monochromatic empty triangles in two-colored point sets. Discret. Appl. Math. 161(9), 1259–1261 (2013)

    Article  MathSciNet  Google Scholar 

  30. Sakai, T., Urrutia, J.: Convex decompositions of point sets in the plane. In: Proc. Japan Conference on Computational Geometry anf Graphs (JCCGG2009), Kanazawa, Japan, pp. 15-16 (2009)

  31. Sakai, T., Urrutia, J.: Covering the convex quadrilaterals of point sets. Graphs Comb. 23, 343–358 (2007)

    Article  MathSciNet  Google Scholar 

  32. Souvaine D., Tóth C., A. Winslow A.: Simultaneously flippable edges in triangulations, Computational Geometry, Lecture Notes in Computer Science, Vol. 7579, pp. 138-145 (2012)

    MATH  Google Scholar 

  33. Szekeres, G., Peters, L.: Computer solution to the 17-point Erdös-Szekeres problem. ANZIAM J. 48(2), 151–164 (2006)

    Article  MathSciNet  Google Scholar 

  34. Tóth, G., Valtr, P.: The Erdös-Szekeres theorem: upper bounds and related results. Comb. Comput. Geom. 52, 557–568 (2005)

    MATH  Google Scholar 

  35. Valtr, P.: On empty hexagons, in J. E. Goodman, J. Pach, R. Pollack, Surveys on Discrete and Computational Geometry, Twenty Years Later, AMS, pp. 433-441 (2008)

Download references

Author information

Authors and Affiliations

  1. Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México, México, México

    Jorge Cravioto-Lagos & Alejandro Corinto González-Martínez

  2. Department of Mathematics, Tokai University, Tokyo, Japan

    Toshinori Sakai

  3. Instituto de Matemáticas, Universidad Nacional Autónoma de México, México, México

    Jorge Urrutia

Authors
  1. Jorge Cravioto-Lagos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alejandro Corinto González-Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Toshinori Sakai
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jorge Urrutia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Toshinori Sakai.

Additional information

Publisher's Note

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

J. Cravioto-Lagos: Research supported by CONACyT Grant number 178379

Alejandro Corinto González-Martínez: Research supported by CONACyT Grant number 178379

Jorge Urrutia: Research supported by CONACyT Grant number 178379, and by PAPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica, UNAM.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cravioto-Lagos, J., González-Martínez, A.C., Sakai, T. et al. On Almost Empty Monochromatic Triangles and Convex Quadrilaterals in Colored Point Sets. Graphs and Combinatorics 35, 1475–1493 (2019). https://doi.org/10.1007/s00373-019-02081-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02081-8

Keywords

Search

Navigation