Decompositions, partitions, and coverings with convex polygons and pseudo-triangles

O. Aichholzer, C. Huemer, S. Kappes, B. Speckmann, Cs.D. Tóth

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

12 Citaten (Scopus)


We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets.
Originele taal-2Engels
Pagina's (van-tot)481-507
TijdschriftGraphs and Combinatorics
Nummer van het tijdschrift5
StatusGepubliceerd - 2007


Duik in de onderzoeksthema's van 'Decompositions, partitions, and coverings with convex polygons and pseudo-triangles'. Samen vormen ze een unieke vingerafdruk.

Citeer dit