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?

  • Just out of curiosity, what are some applications of this problem? – Mehrdad Jan 3 '16 at 7:12
  • 2
    @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
  • Cool, thanks! :) – Mehrdad Jan 3 '16 at 8:09
up vote 14 down vote accepted

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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