On Pseudo-Convex Partitions of a Planar Point Set

Abstract

Aichholzer et al. [{\it Graphs and Combinatorics}, Vol. 23, 481-507, 2007] introduced the notion of pseudo-convex partitioning of planar point sets and proved that the pseudo-convex partition number $ψ(n)$ satisfies, $\frac{3}{4}\lfloor\frac{n}{4}\rfloor\leq ψ(n)\leq\lceil\frac{n}{4}\rceil$. In this paper we prove that $ψ(13)=3$, which immediately improves the upper bound on $ψ(n)$ to $\lceil\frac{3n}{13}\rceil$, thus answering a question posed by Aichholzer et al. in the same paper.

Typos corrected and slightly reorganized. 11 pages, 5 figures