R help - Mar 2010 - Find a rectangle of maximal area

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.

Thanks in advance for any suggestions,
Hans Werner

P.S.: Example "Is this rectangle of maximal area?"
----
n <- 100; set.seed(832)
x <- runif(n); y <- runif(n)
plot(c(0,1), c(0,1), type="n", axes=FALSE, asp=1,
     xlab="", ylab="", main="Rectangle Problem",
sub="")
rect(0,0,1,1, col="darkblue")
xl<-100; yu<-43; xr<-40; yo<-3
area <- (x[xr]-x[xl])*(y[yo]-y[yu])
rect(x[xl], y[yu], x[xr], y[yo],
     lty=2, col="darkblue", border="red")
text((x[xl]+x[xr])/2, (y[yu]+y[yo])/2,
     paste("area =", round(area, 4)), cex=0.75, col="red")
points(x, y, pch=20, col="white")
----

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

Hans W Borchers <hwborchers <at> googlemail.com> writes:
> 
> 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.
> 
> Thanks in advance for any suggestions,
> Hans Werner
> 

I solved this with a simple minded MINLP formulation using BARON (a global 
solver). 
This seems to produce solutions relatively quickly (somewhat slower for n=200). 
Actually this solved easier than I expected. See:

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

----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin at amsterdamoptimization.com
http://amsterdamoptimization.com