O. Aichholzer, C. Huemer, S. Kappes, B. Speckmann, and C. D. Tóth
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.