2026-04-05T10:43:51Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/856132026-01-26T02:12:21Zcom_2072_1033col_2072_452950

On k-gons and k-holes in point sets Aichholzer, Oswin Fabila Monroy, Ruy Gonzalez Aguilar, Hernan Hackl, Thomas Heredia, Marco A. Huemer, Clemens Urrutia Galicia, Jorge Valtr, Pavel Vogtenhuber, Birgit Àrees temàtiques de la UPC::Matemàtiques i estadística Graph theory Erdos-Szekeres type problems k-Gons k-Holes Empty k-gons empty convex polygons lower bounds number Grafs, Teoria de We consider a variation of the classical Erdos-Szekeres problems on the existence and number of convex k-gons and k-holes (empty k-gons) in a set of n points in the plane. Allowing the k-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any k and sufficiently large n, we give a quadratic lower bound for the number of k-holes, and show that this number is maximized by sets in convex position. (C) 2014 Elsevier B.V. All rights reserved. Postprint (author's final draft) 2015-08-01 Article http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access