Abstract
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 language | English |
---|---|
Pages (from-to) | 481-507 |
Journal | Graphs and Combinatorics |
Volume | 23 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2007 |