Abstract
Given a set P of n points in the plane, in general position, denote by \(N_\varDelta (P)\) the number of empty triangles with vertices in P. In this paper we investigate by how much \(N_\varDelta (P)\) changes if a point x is removed from P. By constructing a graph \(G_P(x)\) based on the arrangement of the empty triangles incident on x, we transform this geometric problem to the problem of counting triangles in the graph \(G_P(x)\). We study properties of the graph \(G_P(x)\) and, in particular, show that it is kite-free. This relates the growth rate of the number of empty triangles to the famous Ruzsa-Szemerédi problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bárány, I., Füredi, Z.: Empty simplices in Euclidean space. Can. Math. Bull. 30(4), 436–445 (1987)
Bárány, I., Marckert, J.-F., Reitzner, M.: Many empty triangles have a common edge. Discrete Comput. Geom. 50, 244–252 (2013). https://doi.org/10.1007/s00454-013-9506-0
Bárány, I., Valtr, P.: Planar point sets with a small number of empty convex polygons. Stud. Sci. Math. Hung. 41(2), 243–269 (2004)
Behrend, F.A.: On sets of integers which contain no three terms in arithmetical progression. Proc. Natl. Acad. Sci. 32(12), 331–332 (1946)
Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry, vol. 18. Springer, New York (2005). https://doi.org/10.1007/0-387-29929-7
Erdos, P.: On some unsolved problems in elementary geometry. Mat. Lapok 2(2), 1–10 (1992)
Fox, J.: A new proof of the graph removal lemma. Ann. Math. 174(1), 561–579 (2011)
García, A.: A note on the number of empty triangles. In: Márquez, A., Ramos, P., Urrutia, J. (eds.) EGC 2011. LNCS, vol. 7579, pp. 249–257. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34191-5_24
Kővári, T., Sós, V.T., Turán, P.: On a problem of Zarankiewicz. In: Colloquium Mathematicum, vol. 3, pp. 50–57. Polska Akademia Nauk (1954)
Pinchasi, R., Radoičić, R., Sharir, M.: On empty convex polygons in a planar point set. J. Comb. Theory Ser. A 3(113), 385–419 (2006)
Reitzner, M., Temesvari, D.: Stars of empty simplices. arXiv preprint arXiv:1808.08734 (2018)
Ruzsa, I.Z., Szemerédi, E.: Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976) Coll. Math. Soc. J. Bolyai 18(939–945), 2 (1978)
Szemerédi, E.: Regular partitions of graphs. Computer Science Department, Stanford University (1975)
Valtr, P.: On the minimum number of empty polygons in planar point sets. Stud. Sci. Math. Hung. 30, 155–163 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bhattacharya, B.B., Das, S., Islam, S.S., Sen, S. (2024). Growth Rate of the Number of Empty Triangles in the Plane. In: Kalyanasundaram, S., Maheshwari, A. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2024. Lecture Notes in Computer Science, vol 14508. Springer, Cham. https://doi.org/10.1007/978-3-031-52213-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-52213-0_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-52212-3
Online ISBN: 978-3-031-52213-0
eBook Packages: Computer ScienceComputer Science (R0)