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

• @Mehrdad it is related to my research about fair division of land. I started from the following variation on the fair-cake-cutting problem: --- "A father has a square land-plot and $n$ children. Each child has a different value-measure regarding the land-plot. The father wants to give each child a land-plot with a positive measure. Then, he wants to leave for himself a rectangular land-plot as large as possible." --- Apparently, the worst case is that each child wants a very specific location (a point). Then, the problem reduces to what I asked above. – Erel Segal-Halevi Jan 3 '16 at 7:25
There is an $O(n \log^2 n)$ time algorithm. [Aggarwal and Suri 87]