Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On k-gons and k-holes in point sets

Autor
Aichholzer, O.; Fabila, R.; Gonzalez, H.; Hackl, T.; Heredia, M.; Huemer, C.; URRUTIA, J.; Valtr, P.; Vogtenhuber, B.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2015-08-01
Volum
48
Número
7
Pàgina inicial
528
Pàgina final
537
DOI
https://doi.org/10.1016/j.comgeo.2014.12.007 Obrir en finestra nova
Projecte finançador
Morfología geométrica computacional.
Puntos y grafos: puentes geométricos (IP04 en CRP Comb. of points sets, ComPoSe,EuroGIGA ESF)
Repositori
http://hdl.handle.net/2117/85613 Obrir en finestra nova
Resum
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 ri...
Citació
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.
Paraules clau
Erdos-szekeres Type Problems, K-gons, K-holes, Empty K-gons, Empty Convex Polygons, Lower Bounds, Number
Grup de recerca
DCCG - Grup de recerca en geometria computacional, combinatoria i discreta

Participants

  • Aichholzer, Oswin  (autor)
  • Fabila Monroy, Ruy  (autor)
  • Gonzalez Aguilar, Hernan  (autor)
  • Hackl, Thomas  (autor)
  • Heredia, Marco A.  (autor)
  • Huemer, Clemens  (autor)
  • Urrutia Galicia, Jorge  (autor)
  • Valtr, Pavel  (autor)
  • Vogtenhuber, Birgit  (autor)

Arxius