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 $\psi (n)$ satisfies, $\frac{3}{4}\lfloor \frac{n}{4}\rfloor \le \psi (n)\le \lceil \frac{n}{4}\rceil$. In this paper we prove that $\psi (13)=3$, which immediately improves the upper bound on $\psi (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