On Pseudo-Convex Partitions of a Planar Point Set

Bhaswar B. Bhattacharya, Sandip Das

Published 2010-11-08, updated 2013-07-03Version 2

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\leq \psi(n)\leq\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.