dc.contributor
Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor
Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
dc.contributor.author
Aichholzer, Oswin
dc.contributor.author
Fabila Monroy, Ruy
dc.contributor.author
Gonzalez Aguilar, Hernan
dc.contributor.author
Hackl, Thomas
dc.contributor.author
Heredia, Marco A.
dc.contributor.author
Huemer, Clemens
dc.contributor.author
Urrutia Galicia, Jorge
dc.contributor.author
Valtr, Pavel
dc.contributor.author
Vogtenhuber, Birgit
dc.date.issued
2015-08-01
dc.identifier
Aichholzer, O., Fabila, R., Gonzalez, H., Hackl, T., Heredia, M., Huemer, C., URRUTIA, J., Valtr, P., Vogtenhuber, B. On k-gons and k-holes in point sets. "Computational geometry: theory and applications", 01 Agost 2015, vol. 48, núm. 7, p. 528-537.
dc.identifier
https://hdl.handle.net/2117/85613
dc.identifier
10.1016/j.comgeo.2014.12.007
dc.description.abstract
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.
dc.description.abstract
Postprint (author's final draft)
dc.format
application/pdf
dc.rights
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject
Àrees temàtiques de la UPC::Matemàtiques i estadística
dc.subject
Erdos-Szekeres type problems
dc.subject
empty convex polygons
dc.subject
Grafs, Teoria de
dc.title
On k-gons and k-holes in point sets
