Polygon within polygon generalization problem 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 &lt;= m &lt; 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.
I don't know how your polygons look, but perhaps a simplified version of the Ramer–Douglas–Peucker algorithm is enough:


for each convex part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;
for each concave part, calculate the area $B_k$ of of the two triangles $P_i P'_i P_{i+1}$ and $P_{i+1} P'_{i+2} P_{i+2}$ formed by the extension of the two points $P_i, P_{i+2}$ and the middle point $P_{i+1}$
calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);
loop until $n-m$ points have been deleted.



The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.

For more complex algorithms you can search for "polygon generalization techniques" though your first condition (points in A are contained in B) implies some additional scaling operations.