Minimal Convex Decompositions

Abstract

Let $P$ be a set of $n$ points on the plane in general position. We say that a set $\Gamma$ of convex polygons with vertices in $P$ is a convex decomposition of $P$ if: Union of all elements in $\Gamma$ is the convex hull of $P,$ every element in $\Gamma$ is empty, and for any two different elements of $\Gamma$ their interiors are disjoint. A minimal convex decomposition of $P$ is a convex decomposition ${\Gamma }^{\prime }$ such that for any two adjacent elements in ${\Gamma }^{\prime }$ its union is a non convex polygon. It is known that $P$ always has a minimal convex decomposition with at most $\frac{3n}{2}$ elements. Here we prove that $P$ always has a minimal convex decomposition with at most $\frac{10n}{7}$ elements.