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

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

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (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.
Original languageEnglish
Pages (from-to)481-507
JournalGraphs and Combinatorics
Issue number5
Publication statusPublished - 2007


Dive into the research topics of 'Decompositions, partitions, and coverings with convex polygons and pseudo-triangles'. Together they form a unique fingerprint.

Cite this