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?

  • $\begingroup$ Just out of curiosity, what are some applications of this problem? $\endgroup$
    – user541686
    Jan 3, 2016 at 7:12
  • 2
    $\begingroup$ @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. $\endgroup$ Jan 3, 2016 at 7:25

1 Answer 1


There is an $O(n \log^2 n)$ time algorithm. [Aggarwal and Suri 87]

It seems to be the state of the art.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.