Problem: You have a set of n ordered x,y points that form a contour of polygon A that may or may not be concave. You must create a new polygon B with m points such that:

1. all points in A are contained within B
2. 20 <= m < n
3. B is the polygon in the set of all Bs with the smallest area
4. the algorithm must be reasonably fast and not overly complicated (i.e. no fast-fourier transforms lol!)

The input to the algorithm is polygon A and "m".

I'd like (3) to be the optimal solution but it doesn't have to be since I think this would make the problem NP-hard. This solution is for practical purposes so I'm really looking for a practical solution. (1) Is critical so whatever the solution is it should be trivial to prove that (1) holds true.

Have a few solutions so far:

1. B is a rectangle.
2. B is a circle with m points.
3. Construct B from A by removing concave points. Doesn't work with non-concave polygons however : /
4. Construct B from A by looping through each point "a" and taking the next two points "b" and "c". Then create a ray "ab" through "a" and "b". Move point "c" the minimum distance such that it is on the ray "ab". Remove point "b". This method doesn't always work and I have found cases where it will fail to with rule (1).
5. Draw a triangle around the polygon and use rays to iteratively slice away the sub-section with the largest area that contains no points from Polygan A. Starting Triangle can get very stretched with certain shapes like elipses and "might" cause floating point issues.
6. Same concept as 5 above with the triangle, but instead create a circle of M points and iteratively slice away at the circle.

Each solutions is terrible in its own way. Some have issues with convex shapes, others with concave shapes. The shapes that cause the most problems in general tend to be U shapes and elipses. There are also problems with the iterative slicing approaches. Iterative Slicing can yield a polygon B with the tendency of being inaccurate on one side while a perfect fit on the other side. This issue is most noticeable when polygon A is a circle. Randomizing the slicing a bit will also only yield an abomination that might not even resemble the original shape, especially if it is a circle.