Minimum-area bounding quadrilateral algorithm - MathOverflow

Minimum-area bounding quadrilateral algorithm

2010-01-12T20:19:56Z

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), 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!)

Answer by David Eppstein for Minimum-area bounding quadrilateral algorithm

2010-01-12T21:09:32Z

I think what you want is "Geometric applications of a matrix searching algorithm", Aggarwal et al, Algorithmic 1987, doi: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).

Answer by Michael Lugo for Minimum-area bounding quadrilateral algorithm

2010-01-12T21:28:21Z

I like the Monte Carlo algorithm suggested by Carl Smotricz at Stack Overflow, which I'll quote here:

For each trial, randomly select p distinct vertices and q distinct sides of the polygon such that p + q = 4.
For each of the q sides, construct a line passing through that side's endpoints.
For each of the p vertices, construct a line passing through that vertex and with a randomly assigned slope.
Verify that the 4 lines indeed form a quadrilateral, and that this quadrilateral contains (and does not intersect!) the polygon. If these tests fail, don't pursue this iteration any further.
If this quadrilateral's area is the minimum of all areas seen so far, remember the area and the coordinates of the quadrilateral's vertices.
Repeat an arbitrary number of times, and return the "best" quadrilateral found.

But surely this can be improved upon. In particular, the "best" quadrilateral here is not guaranteed to touch the polygon we're attempting to bound, and so it can be made smaller. In particular, it seems like making random guesses and then trying to "improve" them in some way would be better than just making random guesses and throwing them out if they're not good enough.