# [R] Find a rectangle of maximal area

Erwin Kalvelagen erwin.kalvelagen at gmail.com
Mon Mar 22 06:05:09 CET 2010

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

```