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

About Pulkit Parikh

A computer science researcher by training. At present, I earn my monthly wages from Microsoft, where I am a software engineer. Prior to that, I had worked with KSS and HP Labs, after obtaining MS-by-Research from IIIT Hyderabad. I hail from Ahmedabad (Gujarat), where I spent the first two decades of my life. A few years later, Sejal was kind enough to pick me as her partner for life. I am avidly fond of bridge (a riveting mind game of cards). In late 2010, I made what I consider my most significant decision: https://pulzinponderland.wordpress.com/living-well-by-letting-live/

Posted on October 15, 2007, in General Musings and tagged , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: