On Pseudo-Convex Decompositions, Partitions, and Coverings

O. Aichholzer, C. Huemer, S. Renkl, B. Speckmann, and C. D. Tóth

Abstract:

We introduce pseudo-convex decompositions, partitions, and coverings for planar point sets. They are natural extensions of their convex counterparts that use both convex polygons and pseudo-triangles. We discuss some of their basic combinatorial properties and establish upper and lower bounds on their complexity.

Reference: O. Aichholzer, C. Huemer, S. Renkl, B. Speckmann, and C. D. Tóth. On pseudo-convex decompositions, partitions, and coverings. In Proc. $21^{th}$ European Workshop on Computational Geometry EWCG '05, pages 89-92, Eindhoven, The Nederlands, 2005.