×

zbMATH — the first resource for mathematics

Lower bounds for the number of small convex \(k\)-holes. (English) Zbl 1287.65011
Let \(S\) be a set of \(n\) points in the plane such that no three points of \(S\) lie on a common straight line and a simple polygon \(P\), spanned by \(k\)-points from \(S\), is called a \(k\)-hole of \(S\) if no other point of \(S\) is contained in the interior of \(P\). Denoting the least number of convex \(k\)-holes in \(S\) by \(h_k(n)\), the authors first obtain a better lower bound for \(h_5(n)\), especially for small values of \(n\) by fine tuning the proof given by O. Aichholzer et al. [Lecture Notes in Computer Science 7579, 1–13 (2012; Zbl 1374.52020)]. Better lower bounds for the number of empty triangles and convex 4-holes which are in certain sense generated by convex 5-holes, are been obtained by using a recent result of A. García [Lecture Notes in Computer Science 7579, 249–257 (2012; Zbl 1374.68663)].

MSC:
65D18 Numerical aspects of computer graphics, image analysis, and computational 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, (Proc. XIII Encuentros de Geometría Computacional (EGC 2009), Zaragoza, Spain, (2009)), 43-52
[2] Aichholzer, O.; Fabila-Monroy, R.; Hackl, T.; Huemer, C.; Pilz, A.; Vogtenhuber, B., Lower bounds for the number of small convex k-holes, (Proc. 24th Annual Canadian Conference on Computational Geometry (CCCG 2012), Charlottetown, PEI, Canada, (2012)), 247-252
[3] Aichholzer, O.; Hackl, T.; Vogtenhuber, B., On 5-holes and 5-gons, (Proc. XIV Encuentros de Geometría Computacional (EGC 2011), Alcalá de Henares, Spain, (2011)), 7-10
[4] Aichholzer, O.; Hackl, T.; Vogtenhuber, B., On 5-holes and 5-gons, (Marquez, A.; Ramos, P.; Urrutia, J., Computational Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, Festschrift Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Lect. Notes Comput. Sci. (LNCS), vol. 7579, (2012), Springer), 1-13, Revised Selected Papers · Zbl 1374.52020
[5] Bárány, I.; Füredi, Z., Empty simplices in Euclidean space, Can. Math. Bull., 30, 436-445, (1987) · Zbl 0639.52006
[6] Bárány, I.; Károlyi, G., Problems and results around the Erdős-Szekeres convex polygon theorem, (Akiyama, J.; Kano, M.; Urabe, M., Discrete and Computational Geometry, Lect. Notes Comput. Sci. (LNCS), vol. 2098, (2001), Springer), 91-105 · Zbl 0998.52004
[7] Bárány, I.; Valtr, P., Planar point sets with a small number of empty convex polygons, Studia Sci. Math. Hung., 41, 243-266, (2004) · Zbl 1075.52008
[8] Dehnhardt, K., Leere konvexe vielecke in ebenen punktmengen, (1987), TU Braunschweig, Germany, in German · Zbl 0629.52016
[9] Edelsbrunner, H., Algorithms in combinatorial geometry, (1987), Springer · Zbl 0634.52001
[10] Erdős, P., Some more problems on elementary geometry, Aust. Math. Soc. Gaz., 5, 52-54, (1978) · Zbl 0417.52002
[11] García, A., A note on the number of empty triangles, (Proc. XIV Encuentros de Geometría Computacional (EGC 2011), Alcalá de Henares, Spain, (2011)), 101-104
[12] García, A., A note on the number of empty triangles, (Marquez, A.; Ramos, P.; Urrutia, J., Computational Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, Festschrift Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Lect. Notes Comput. Sci. (LNCS), vol. 7579, (2012), Springer), 249-257, Revised Selected Papers · Zbl 1374.68663
[13] Gerken, T., Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1-3, 239-272, (2008) · Zbl 1184.52016
[14] Harborth, H., Konvexe Fünfecke in ebenen punktmengen, Elem. Math., 33, 116-118, (1978), in German · Zbl 0397.52005
[15] Horton, J., Sets with no empty convex 7-gons, Can. Math. Bull., 26, 4, 482-484, (1983) · Zbl 0521.52010
[16] Nicolás, C., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397, (2007) · Zbl 1146.52010
[17] Pinchasi, R.; Radoičić, R.; Sharir, M., On empty convex polygons in a planar point set, J. Comb. Theory, Ser. A, 113, 385-419, (2006) · Zbl 1088.52500
[18] Valtr, P., On empty pentagons and hexagons in planar point sets, (Proc. 18th Computing: Australasian Theory Symposium (CATS 2012), Melbourne, Australia, (2012)), 47-48
[19] Vogtenhuber, B., Combinatorial aspects of [colored] point sets in the plane, (2011), Institute for Software Technology, Graz University of Technology Graz, Austria, Ph.D. thesis
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.