Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On k-convex point sets

Autor
Aichholzer, O.; Aurenhammer, F.; Hackl, T.; Hurtado, F.; Pilz, A.; Ramos, P.; URRUTIA, J.; Valtr, P.; Vogtenhuber, B.
Tipus d'activitat
Article en revista
Revista
Computational geometry: theory and applications
Data de publicació
2014-09-01
Volum
47
Número
8
Pàgina inicial
809
Pàgina final
832
DOI
https://doi.org/10.1016/j.comgeo.2014.04.004 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0925772114000534 Obrir en finestra nova
Resum
We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n-point set contains a subset of O(log2n) points that are in 2-convex position. This bound is asymptotically tight. ...
Paraules clau
Convexity, Erdos-Szekeres problem, Polygonization
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Aichholzer, Oswin  (autor)
  • Aurenhammer, Franz  (autor)
  • Hackl, Thomas  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Pilz, Alexander  (autor)
  • Ramos Alonso, Pedro Antonio  (autor)
  • Urrutia Galicia, Jorge  (autor)
  • Valtr, Pavel  (autor)
  • Vogtenhuber, Birgit  (autor)