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...

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)