Largest empty rectangle

<h2 id="classification">Classification</h2>
<p>In terms of size measure, the two most common cases are the largest-area empty rectangle and largest-perimeter empty rectangle.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p><p>Another major classification is whether the rectangle is sought among <a href="/facts/Axis-oriented/Vej1lrE5">axis-oriented</a> or arbitrarily oriented rectangles.
</p>
<h2 id="special-cases">Special cases</h2>
<h3>Maximum-area square</h3>
<p>The case when the sought rectangle is an axis-oriented square may be treated using <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagrams</a> in 
  
    
      
        
          L
          
            1
          
        
      
    
    {\displaystyle L_{1}}
  
metrics for the corresponding obstacle set, similarly to the <a href="/facts/Largest_empty_circle/3dVovPgR">largest empty circle</a> problem. In particular, for the case of points within rectangle an optimal algorithm of <a href="/facts/Time_complexity/77T62gmf">time complexity</a> 
  
    
      
        Θ
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle \Theta (n\log n)}
  
 is known.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>
<h3>Domain: rectangle containing points</h3>
<p>A problem first discussed by Naamad, Lee and Hsu in 1983<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> is stated as follows: given a rectangle <i>A</i> containing <i>n</i> points, find a largest-area rectangle with sides parallel to those of <i>A</i> which lies within <i>A</i> and does not contain any of the given points. Naamad, Lee and Hsu presented an algorithm of <a href="/facts/Time_complexity/77T62gmf">time complexity</a> 
  
    
      
        O
        (
        min
        (
        
          n
          
            2
          
        
        ,
        s
        log
        ⁡
        n
        )
        )
      
    
    {\displaystyle O(\min(n^{2},s\log n))}
  
, where <i>s</i> is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that 
  
    
      
        s
        =
        O
        (
        
          n
          
            2
          
        
        )
      
    
    {\displaystyle s=O(n^{2})}
  
 and gave an example in which <i>s</i> is quadratic in <i>n</i>. Afterwards a number of papers presented better algorithms  for the problem.
</p>
<h3>Domain: line segment obstacles</h3>
<p>The problem of empty isothetic rectangles among <a href="/facts/Isothetic_polygon/R18UGWMw">isothetic</a> line segments was first considered<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> in 1990.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>
</p>
<h2 id="generalizations">Generalizations</h2>
<h3>Higher dimensions</h3>
<p>In 3-dimensional space,  algorithms are known for finding a largest maximal empty isothetic <a href="/facts/Cuboid/eLLKX4rh">cuboid</a> problem, as well as for enumeration of all maximal isothetic empty cuboids.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Largest_empty_sphere/3dVovPgR">Largest empty sphere</a></li>
<li><a href="/facts/Minimum_bounding_box/oFHL8bxI">Minimum bounding box</a>, <a href="/facts/Minimum_bounding_rectangle/yfDEoK8d">Minimum bounding rectangle</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"Search Google Scholar for "largest empty rectangle" term usage". <a href="https://scholar.google.com/scholar?hl=en&q=largest+empty+rectangle" target="_blank">https://scholar.google.com/scholar?hl=en&q=largest+empty+rectangle</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Search Google Scholar for "maximal empty rectangle" term usage". <a href="https://scholar.google.com/scholar?hl=en&q=maximal+empty+rectangle" target="_blank">https://scholar.google.com/scholar?hl=en&q=maximal+empty+rectangle</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>"Search Google Scholar for "maximum empty rectangle" term usage". <a href="https://scholar.google.com/scholar?hl=en&q=maximum+empty+rectangle" target="_blank">https://scholar.google.com/scholar?hl=en&q=maximum+empty+rectangle</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Jeffrey Ullman (1984). "Ch.9: Algorithms for VLSI Design Tools". Computational Aspects of VLSI. Computer Science Press. ISBN 0-914894-95-1. describes algorithms for polygon operations involved in electronic design automation (design rule checking, circuit extraction, placement and routing). <a href="0-914894-95-1" target="_blank">0-914894-95-1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Baird, H. S., Jones, S. E., Fortune, S.J. (1990). "Image segmentation by shape-directed covers". [1990] Proceedings. 10th International Conference on Pattern Recognition. Vol. 1. pp. 820–825. doi:10.1109/ICPR.1990.118223. ISBN 0-8186-2062-5. S2CID 62735730.{{cite book}}:  CS1 maint: multiple names: authors list (link) <a href="0-8186-2062-5" target="_blank">0-8186-2062-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Alok Aggearwal, Subhash Suri (1987). "Fast algorithms for computing the largest empty rectangle". Proceedings of the third annual symposium on Computational geometry - SCG '87. pp. 278–290. doi:10.1145/41958.41988. ISBN 0897912314. S2CID 18500442. <a href="0897912314" target="_blank">0897912314</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>B. Chazelle, R. L. Drysdale III and D. T. Lee (1984). "Computing the largest empty rectangle". STACS-1984, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 166: 43–54. doi:10.1007/3-540-12920-0_4. ISBN 978-3-540-12920-2. <a href="978-3-540-12920-2" target="_blank">978-3-540-12920-2</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>A. Naamad, D. T. Lee and W.-L. Hsu (1984). "On the Maximum Empty Rectangle Problem". Discrete Applied Mathematics. 8 (3): 267–277. doi:10.1016/0166-218X(84)90124-0. <a href="/wiki/D._T._Lee" target="_blank">/wiki/D._T._Lee</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Thiagarajan, P. S. (23 November 1994). "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. Springer. p. 159. ISBN 9783540587156. <a href="9783540587156" target="_blank">9783540587156</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Subhas C Nandy; Bhargab B Bhattacharya; Sibabrata Ray (1990). "Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design". Proc. FST & TCS – 10, Lecture Notes in Computer Science. Lecture Notes in Computer Science. 437: 255–269. doi:10.1007/3-540-53487-3_50. ISBN 978-3-540-53487-7. <a href="978-3-540-53487-7" target="_blank">978-3-540-53487-7</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Thiagarajan, P. S. (23 November 1994). "Location of Largest Empty Rectangle among Arbitrary Obstacles". Foundations of Software Technology and Theoretical Computer Science. Springer. p. 159. ISBN 9783540587156. <a href="9783540587156" target="_blank">9783540587156</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>S.C. Nandy; B.B. Bhattacharya (1998). "Maximal Empty Cuboids among Points and Blocks". Computers & Mathematics with Applications. 36 (3): 11–20. doi:10.1016/S0898-1221(98)00125-4. <a href="https://doi.org/10.1016%2FS0898-1221%2898%2900125-4" target="_blank">https://doi.org/10.1016%2FS0898-1221%2898%2900125-4</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
</ol>

Largest empty rectangle open-in-new

Largest empty rectangle