×

zbMATH — the first resource for mathematics

A note on the number of empty triangles. (English) Zbl 1374.68663
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 249-257 (2012).
Summary: Let \(P\) be a set of \(n\) points on the plane, in general position, \(H\) of them placed on the boundary of the convex hull of \(P\). In this note we prove that there is a well defined family of empty triangles, the family of empty triangles not generated by an empty convex pentagon, containing exactly \(n^{2}-5n+H+4\) empty triangles. This result immediately implies a slight improvement on the lower bound on the number of empty triangles that every set of \(n\) points in the plane must determine.
For the entire collection see [Zbl 1253.68016].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52C10 Erdős problems and related topics of discrete geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aichholzer, O.: [Empty] [colored] k-gons - Recent results on some Erdös-Szekeres type problems. In: Proc. XIII Encuentros de Geometría Computacional, pp. 43–52. Prensas universitarias de Zaragoza, Spain (2009)
[2] 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) · Zbl 1075.52008
[3] Bàràny, I., Füredi, Z.: Empty simplices in Euclidean space. Canadian Math. Bull. 30, 436–445 (1987) · Zbl 0639.52006 · doi:10.4153/CMB-1987-064-1
[4] Dehnhardt, K.: Leere konvexe Vielecke in ebenen Punktmengen, Dissertation, TU Braunschweig (1987) · Zbl 0629.52016
[5] Harborth, H.: Konvexe Fünfecke in ebenen Punktmengen. Elem. Math. 33, 116–118 (1978) · Zbl 0397.52005
[6] Morris, W., Soltan, V.: The Erdös-Szekeres problem on points in convex position - a survey. Bulletin (new series) of the American Mathematical Society 37(4), 437–458 (2000) · Zbl 0958.52018 · doi:10.1090/S0273-0979-00-00877-6
[7] Pinchasi, R., Radoicic, R., Sharir, M.: On empty convex polygons in a planar point set. J. Comb. Theory, Ser. A 113(3), 385–419 (2006) · Zbl 1088.52500 · doi:10.1016/j.jcta.2005.03.007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.