Largest rectangle not touching any rock in a square field Following this mathematical question, I am interested in the algorithmic question:


  Given $n$ points in the unit square, 
  find the largest area of an axis-parallel rectangle in the unit square
  that does not contain any of the given points in its interior.


What is known about this problem?
There is an $O(n \log^2 n)$ time algorithm. [Aggarwal and Suri 87]
It seems to be the state of the art.