[R] Find a rectangle of maximal area

[Hans W Borchers]

Barry Rowlingson <b.rowlingson <at> lancaster.ac.uk> writes:

> 
> On Mon, Mar 22, 2010 at 4:28 PM, Hans W Borchers
> <hwborchers <at> googlemail.com> wrote:
> 
> > 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.
> >
> 
> Is this the 'Largest Empty Rectangle' problem?
> 
> http://en.wikipedia.org/wiki/Largest_empty_rectangle

Dear Barry,

thanks for this pointer. I never suspected this problem could have a name of its
own. Rethinking the many possible applications makes it clear: I should have
searched for it before.

I looked in some of the references of the late 80s and found two algorithms 
that appear to be appropriate for implementation in R. The goal is to solve the
problem for n=200 points in less than 10-15 secs.

Thanks again, Hans Werner


> I had a look at some of the references from Wikipedia, but they all
> follow a similar pattern, one I have noticed in many computer science
> journal articles:
> 
>  1. State a problem that looks tricky.
>  2. Say "We have an efficient algorithm for the problem stated in #1"
>  3. Proceed to derive, using much algebra and theory, the efficient algorithm.
>  4. Stop.
> 
> The idea of actually producing some dirty, filthy, actual code to
> implement their shiny algorithms never seems to cross their minds.
> 
>  I also found a similar question from 2008 asked on the R-sig-geo
> mailing list. That didn't get much help either!
> 
> Sorry.
> 
> Barry
> 
>