On 03/21/2010 10:12 PM, Hans W Borchers wrote:
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 know this request is not about R syntax and does not contain 'repro-code'. But
perhaps a somehow similar problem has been solved before.
Hi Hans,
The emptyspace function in the plotrix package is a fairly crude
implementation of this, but the code might give you some ideas.
Jim
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
