Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Lower bounds for the number of small convex k-holes

Autor
Aichholzer, O.; Fabila, R.; Hackl, T.; Huemer, C.; Pilz, A.; Vogtenhuber, B.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2014-07-01
Volum
47
Número
5
Pàgina inicial
605
Pàgina final
613
DOI
https://doi.org/10.1016/j.comgeo.2013.12.002 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)
URL
http://www.sciencedirect.com/science/article/pii/S0925772113001703 Obrir en finestra nova
Resum
Let S be a set of n points in the plane in general position, that is, no three points of S are on a line. We consider an Erdos-type question on the least number h(k)(n) of convex k-holes in S, and give improved lower bounds on h(k)(n), for 3 <= k <= 5. Specifically, we show that h(3)(n) >= n(2) - 32n/7 + 22/7, h(4)(n) >= n(2)/2 - 9n/4 - o(n), and h(5)(n) >= 3n/4 - o(n). We further settle several questions on sets of 12 points posed by Dehnhardt in 1987. (C) 2013 Elsevier B.V. All rights reserved...
Paraules clau
Counting, EMPTY, Empty convex polygon, Erdos-type problem, PLANAR POINT SETS, POLYGONS, THEOREM
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Aichholzer, Oswin  (autor)
  • Fabila Monroy, Ruy  (autor)
  • Hackl, Thomas  (autor)
  • Huemer, Clemens  (autor)
  • Pilz, Alexander  (autor)
  • Vogtenhuber, Birgit  (autor)