Apr 7, 2008

Minimum Bounding Rectangle of a Point Set

Give a 2-D point set, we need to find the minimum bounding rectangle in term of area.

I read it somewhere that the minimum rectangle must always contain at least one edge of the convex hull, however, I can't find a citation now. So the algorithm can be constructed in the following way: first construct the convex hull, then rotate each edges for the convex hull to the position parallel to x-axes, then calculate area of bounding rectangle; find the minimum one of these rotated rectangles and rotate it back to normal.

No comments: