Given segments AB BC CD such that the angle between AC and CD is less than 180 degrees, add the candidate point E where AB CD meet when extended. This is always outside a convex polygon. Choose the next candidate to minimize the area of BEC. The resulting polygon is also convex. Iterate.

Once you reach a rectangle or a triangle there will be no more candidates.

Nice to see that others have the same ideas! I also thought about that option at first, but this adds too much when the angle between AB and CD is small.

So my current approach is to take ABCDE and replace BC and CD with that of the (infinitely many) tangents on C where the resulting area is minimal. Then B' is the intersection of the ray AB with that tangent. D' is corresponding intersection with ray ED. ABCDE is then replaced with AB'D'E (i.e. B->B', C removed, D->D').

Although I didn't yet do the math to find the optimal tangent on each point, it shouldn't be too hard to find that one.

Note that the simple ABCD approach is a degenerate case from this new approach: You just always choose the tangent to be BC. So I expect the new approach to produce strictly better results.

However, is there anything more elaborate than that? I don't belive I'm the first one who formulates that problem...

Yes, there is other work on this problem. My google-fu is strong.

http://archive.org/details/minimumareacircu00agga "We show that the smallest k-gon circumscribing a convex n-gon can be computed in O(n^2 log n log k) time" This is elaborate enough... the paper isn't written in anything like pseudocode.

I'm presuming that that's not the result referred to below though (it's different authors, but this was the same year as the paper above): http://www.sciencedirect.com/science/article/pii/0734189X859... "A recent paper by Dori and Ben-Bassat presented an algorithm for finding a minimal area k-gon circumscribing a given convex n-gon, where k < n. An infinite class of polygons for which their algorithm fails to find the minimal area circumscribing k-gon is presented."

http://www.springerlink.com/content/11373157378222m3/ "Given any plane strictly convex region K and any positive integer n >= 3, there exists an inscribed 2n-gon Q_2n and a circumscribed n-gon P_n such that Area(P_n)/Area(Q_2n) <= secant(pi/n)." (ie this is how much you expand the area when you halve the number of edges)

If nothing else, knowing that the words "minimum circumscribing polygons" is the right thing to google for is useful (not just minimum-area - I presume minimum-perimiter solutions are useful to you too)

Thanks for all those pointers! I think I was missing the keyword "circumscribing".

Invert your polygon (so all points at a distance `x` from the center get moved to a distance `1/x`), apply Visvalingam, then invert the result back.

I don't see how this would help. Visvalingam selects a subset of the inverted points, so when inverting back, I'll still end up with a subset of my original points. So the algorithm still cuts corners instead of adding areas.

If you add a midpoint along each edge Visvalingam creates, invert the reduced poly then remove the original points, you'll get a containing polygon. I think. But we're heading rapidly into hackish bodge territory :-)

This doesn't work. Consider a polygon with all points on the unit circle - your transformation is the identity (both before and after Visvalingam's algorithm is applied).

True.

Try adding addittional points or even smoothing before running the simplification algorithm.