Finding a minimum area rectangle of a convex polygon

Question

I am looking for a efficient way to find a minimum area rectangle of a convex polygon.

running time should be O(n) where n is the number of vertices.

there is a complex algorithm for finind a bounding box of a general polygon, but there should be a easier algorithm for a convex polygon.

How can one do it easily for a convex polygon?

thanks.

Does this answer your question? [Algorithm to find the minimum-area-rectangle for given points in order to compute the major and minor axis length](https://stackoverflow.com/questions/13542855/algorithm-to-find-the-minimum-area-rectangle-for-given-points-in-order-to-comput) — th3g3ntl3man, Jan 28 '22 at 13:39
"there is a complex algorithm for finding a bounding box of a general polygon": could you give a reference ? — Yves Daoust, Jan 28 '22 at 14:21

Yves Daoust · Accepted Answer · 2022-01-28T22:00:09.327

3

Rotating calipers are your best friends.

The tightest bounding rectangle is such that one of its sides coincides with a side of the polygon. So,

starting from an arbitrary side, rotate the polygon to make this side horizontal, at the bottom;
find the three vertices that maximize Y, -X and X respectively (on the figure, 4, 6, and 3). This way, you obtain a bounding box;
then move to the next side, clockwise, and adjust the rotation;
find the next three vertices by updating the maxima (follow the outline and stop before Y decreases; same with -X and X; on the figure, 4->5, 6->6 and 3->3);
for every position, compute the area and keep the best. Stop after a full turn.

It is important to realize that you don't apply the rotations to all vertices, but only when needed. To obtain the initial bounding box, you process O(N) vertices, but the N-1 updates only take O(N) additional work (amortized), and you don't have to compute both coordinates.

edited Jan 28 '22 at 22:00

answered Jan 28 '22 at 14:19

Yves Daoust

53,540
8
41
94

This should also work for arbitrary polygons after first finding the convex hull. – stark Jan 28 '22 at 14:57
@Yves daoust If I understand right, In each iteration you search for the axis parallel rectangle and save the maximum so far? You will do o(n) rotations, Each rotation you need to calculate the rectangle, thats o(n) again meaning o(n^2)? – firev2 Jan 28 '22 at 15:13
@firev2: I forgot to stress that you only compute the rotated vertices *on demand*, i.e. when looking for the maxima. So you only compute a few vertices each time, and the complexity remains O(N). – Yves Daoust Jan 28 '22 at 15:49

Finding a minimum area rectangle of a convex polygon

1 Answers1