Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/85613
Títol: | On k-gons and k-holes in point sets |
---|---|
Autor/a: | Aichholzer, Oswin; Fabila Monroy, Ruy; Gonzalez Aguilar, Hernan; Hackl, Thomas; Heredia, Marco A.; Huemer, Clemens; Urrutia Galicia, Jorge; Valtr, Pavel; Vogtenhuber, Birgit |
Altres autors: | Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
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. |
Matèries: | -À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 |
Drets: | http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Tipus de document: | Article - Versió presentada Article |
Compartir: |