Two-convex polygons

Conference object English OPEN
Aichholzer, Oswin; Aurenhammer, Franz; Hurtado Díaz, Fernando Alfredo; Ramos, Pedro A.; Urrutia, J.;
(2009)
  • Publisher: Université Libre de Bruxelles
  • Subject: Triangulation | Algorithms | Triangulacio | Polygons | :Matemàtiques i estadística::Geometria::Geometria convexa i discreta [Àrees temàtiques de la UPC] | Polígons | Geometria convexa | Algorismes | Convex domains | Convex geometry | Dominis convexos
    arxiv: Computer Science::Computational Geometry | Computer Science::Databases

We introduce a notion of k-convexity and explore some properties of polygons that have this property. In particular, 2-convex polygons can be recognized in O(n log n) time, and k-convex polygons can be triangulated in O(kn) time.
Share - Bookmark