[R] Find a rectangle of maximal area

[Hans W Borchers]

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 rectangle, 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.

And yes, the sides of the rectangle shall be parallel to the sides of the
enclosing unit square (which could be a rectangle of some size, too).

> <snip>
> 
> Thanks in advance for any suggestions,
> Hans Werner

Erwin Kalvelagen <erwin.kalvelagen <at> gmail.com> writes:
>
> 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:

Dear Erwin,

yes, it is possible to emulate an exhaustive search by applying binary
variables and utilizing an MI(N)LP solver. What did you need the'non-
linearity' for? (I am asking as you did not disclose your model.)

The examples on your blog do not take into account that the ratio of longer
to shorter side length of the rectangle shall be smaller than 2. Would it be
difficult to add this restriction to your model?

Unfortunately, there is no free MINLP solver available. Formerly I have called
a Python program to utilize solvers at NEOS. Probably it would be possible to 
write a similar R function to do this.

Still I believe that a clever approach might be possible avoiding the need to
call a commercial solver. I am getting this hope from one of Jon Bentley's
articles in the series Programming Pearls.

Regards,
Hans Werner

P.S.: If you copy my request into your blog, wouldn't it be nice to add a
      pointer back to the R-help entry where this question has been asked?

>     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
>