<p><a href="http://dl.acm.org/citation.cfm?id=41988" rel="noreferrer">There is an <span class="math-container">$O(n \log^2 n)$</span> time algorithm</a>. [Aggarwal and Suri 87]</p>
<p>It seems to be the state of the art.</p>

CC BY-SA 3.0
2016-01-03T06:01:58.413Z
Thanks! After learning that the name of the problem is "largest empty rectangle", I found many other related references: http://www.citeulike.org/user/erelsegal-halevi/tag/largest-rectangle
Erel Segal-Halevi
CC BY-SA 3.0
2016-01-02T23:52:47.753Z
2016-01-02T23:52:47.753Z
2020-06-17T09:38:08.363Z
Chao Xu
<p>Following <a href="https://math.stackexchange.com/questions/1534120/largest-rectangle-not-touching-any-rock-in-a-square-field">this mathematical question</a>, I am interested in the algorithmic question:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>What is known about this problem?</p>

CC BY-SA 3.0
2016-01-03T07:12:26.013Z
Just out of curiosity, what are some applications of this problem?
user541686
CC BY-SA 3.0
2016-01-03T07:25:51.667Z
@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
<cg.comp-geom>
Largest rectangle not touching any rock in a square field
Erel Segal-Halevi
# Largest rectangle not touching any rock in a square field

(Asked by: username_0 on 2016-01-02)

Following [this mathematical question](https://math.stackexchange.com/questions/1534120/largest-rectangle-not-touching-any-rock-in-a-square-field), 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?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: Just out of curiosity, what are some applications of this problem?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2016-01-02. Score: 13 | Accepted answer

[There is an $O(n \log^2 n)$ time algorithm](http://dl.acm.org/citation.cfm?id=41988). [Aggarwal and Suri 87]

It seems to be the state of the art.

> **Comments:**
> **username_0**: Thanks! After learning that the name of the problem is "largest empty rectangle", I found many other related references: http://www.citeulike.org/user/erelsegal-halevi/tag/largest-rectangle  

---

