Given a set P of n points in the plane and a number k, we want to find a polygon C with vertices in P of minimum area that satisfies one of the following properties: (1) C is a convex k-gon, (2) C is an empty convex k-gon, or (3) C contains exactly k points of P and C is the convex hull of these points. We give algorithms for solving each of these three problems in time O(kn3). The space complexity is O(n) for k=4 and O(kn2) for k≥5. The algorithms are based on a dynamic programming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds.
Last update: December 16, 2025.