Finding minimum area \(k\)-gons (Q1186081)

Let \(P\) be a set of \(n\) points in the plane. Assume \(k\geq 3\). The problem considered is to find a convex polygon \(C\) with vertices from \(P\) of minimum area that satisfies one of the following conditions: (1) \(C\) is a convex \(k\)-gon, (2) \(C\) is an empty convex \(k\)-gon (i.e., \(P\cap\text{int} C=\emptyset\)), (3) \(C\) is the convex hull fo exactly \(k\) points of \(P\). It is shown here that each of these problems can be solved by an algorithm of time complexity \(O(kn^ 3)\) and space complexity \(O(kn^ 2)\) (for \(k=4\) this is only \(O(n)\)). The algorithms are based on dynamic programming. The method extends to several similar extremum problems.