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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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
Title of host publicationMathematical Foundations of Computer Science (Proceedings 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006)
EditorsR. Královic, P. Urzyczyn
Place of PublicationBerlin
ISBN (Print)3-540-37791-3
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


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

Cite this