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)