Sunday, March 21, 2010

Looks difficult to me

For an application in image processing -- using R for statistical purposes -- I
need to solve the following task:

Given n (e.g. n = 100 or 200) points in the unit square, more or less randomly
distributed. Find a rectangle of maximal area within the square that does not
contain any of these points in its interior.

If a, b are height and width of the rectangel, other constraints may have to be
imposed such as a, b <= 0.5 and/or 0.5 <= a/b <= 2.0 . The rectangle is
allowed to touch the border of the square.

For each new image the points will be identified by the application, like all
stars of a certain brightness on an astronomical picture. So the task will have
to be performed several times.

I assume this problem is computationally hard. I would like to find a solution
that is reasonably fast for n = 100..200 points. Exhaustive search along the
x, y coordinates of the points will not be fast enough.



I doubt there is easy way to solve this. At least it is not obvious to me.


PS: see also http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult-to-me-2.html