There are a few algorithms around for finding the minimal bounding rectangle (OBB) containing a given (convex) polygon.


Does anybody know about an algorithm for finding a minimal-area bounding quadrilateral (any quadrilateral, not just rectangles)?


I've been refered to this site from stackoverflow.com ([original post](https://stackoverflow.com/questions/2048024/minimum-area-quadrilateral-algorithm)), since the guys over there did not know the answer to this...


(PS: I'm a programmer and not a mathematician, so I would appreciate especially if you could point me to exisiting implementations if there are any... Thanks a lot!)



Minimum-area bounding quadrilateral algorithm
I think what you want is "Geometric applications of a matrix searching algorithm", Aggarwal et al, Algorithmic 1987, [doi:10.1007/BF01840359](http://dx.doi.org/10.1007/BF01840359). It builds on previous work of Aggarwal, Chang, and Yap (their reference [2]) to show that the minimum area enclosing k-gon of a geometric figure can be found in time O(n^2) whenever k is constant — they explain it very briefly towards the bottom of the 11th page of their paper (page 205 of the journal).


