I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical Computer Science" problem.
Problem: Create an algorithm that takes a set of n ordered points in a 2D plane that form the contour of a simple polygon A that may or may not be concave and creates a new polygon B with m points such that:
- all points in A are contained within B
- 3 <= m < n
- B is the polygon in the set of all Bs with the smallest area
- B must be a simple polygon (i.e. no self-intersections).
- The input to the algorithm is polygon A and "m".
- Coincidence of segments in B with segments in A are allowed.
Some example inputs and expected outputs:
- If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
- If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.
Good luck to everyone who tries this problem out. I can promise you this will be very hard especially now that the solution must be optimal.