Blog Archives

An interesting duo of geometric problems

Problem 1: Given a set of 2D points, find an efficient way of computing the least area rectangle that encloses them.

One (probably good) way of approaching this to stamp down on the data size by first showing that the least-area enclosing rectangle of these points is the same as that of the convex hull of the points (For now, I have taken this for granted) and working only on the hull points thereafter.

But, this is just data reduction. How do we use these points to compute the rectangle? The approach I have successfully implemented is not as efficient as I would like it to be. I based my thing on parameterizing the min area rectangle by just the orientation parameter. This is because once the orientation is frozen, once can easily and uniquely determine the min area rectangle by computing minx, maxx, miny, maxy along that and its perpendicular direction. So, it boiled down to optimization in the angle space. Currently, I am using a brute force method but one can study the objective function and better the convergence. However, I have an inkling that there is a non-iterative, closed-form solution to this. To discuss about and arrive at that elegant solution, actually, is the motive of this post.

The second problem is similar but a little more complex. I will post my solution (again, suboptimal) once (and if) there is some interaction about the first one. I will leave you with the problem statement, nevertheless.

Problem 2: Given a set of 2D points, find, efficiently, the maximum area rectangle that is enclosed within their convex hull.

Advertisements