On Optimal $w$-gons in Convex Polygons

Abstract

Let $P$ be a set of $n$ points in ${\mathbb{R}}^2$. For a given positive integer $w<n$, our objective is to find a set $C\subset P$ of points, such that $CH(P\setminus C)$ has the smallest number of vertices and $C$ has at most $n-w$ points. We discuss the $O(w{n}^3)$ time dynamic programming algorithm for monotone decomposable functions (MDF) introduced for finding a class of optimal convex $w$-gons, with vertices chosen from $P$, and improve it to $O(n^3\log w)$ time, which gives an improvement to the existing algorithm for MDFs if their input is a convex polygon.