<p>This problem is a well-known one in <a href="https://en.wikipedia.org/wiki/Computational_geometry" rel="nofollow noreferrer">Computational Geometry</a>. A simplified version of this problem (without a query point) is briefly described <a href="https://en.wikipedia.org/wiki/Largest_empty_rectangle" rel="nofollow noreferrer">here</a>. The problem <em>with</em> query point can be formulated in the following way:</p>
<blockquote>
<p>Let P be a set of n points in a fixed axis-parallel rectangle B in the plane. A P-empty rectangle (or just an empty rectangle for short) is any axis-parallel rectangle that is contained in
B and its interior does not contain any point of P. We consider the problem of preprocessing
P into a data structure so that, given a query point q, we can efficiently find the largest-area
P-empty rectangle containing q.</p>
</blockquote>
<p>The paragraph above has been copied from <a href="https://arxiv.org/abs/1106.3628" rel="nofollow noreferrer">this</a> paper, where authors describe an algorithm and data structure for the set with <code>N</code> points in the plane, which allow to find a maximal empty rectangle for any query point in <code>O(log^4(N))</code> time. Sorry to say, it's a theoretic paper, which doesn't contain any algorithm implementation details.</p>
Find the rectangle with the maximum area, containing a specific point in an occupancy grid
<h1>Problem</h1>
<p>Given an occupancy grid, for example:</p>
<pre><code>...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....
</code></pre>
<p>Where, <code>*</code> represents an occupied block, <code>.</code> represents a free block and <code>X</code> represents a point (or block) of interest, what is the most time-efficient algorithm to find the <strong>largest</strong> rectangle which includes <code>X</code>, but does not include any obstacles, i.e. any <code>*</code>?</p>
<p>For example, the solution to the provided grid would be:</p>
<pre><code>.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....
</code></pre>
<h1>My Thoughts</h1>
<p>Given we have a known starting point <code>X</code>, I can't help but think there must be a straightforwards solution to &quot;snap&quot; lines to the outer boundaries to create the largest rectangle.</p>
<p>My current thinking is to snap lines to the maximum position offsets (i.e. go to the next row or column until you encounter an obstacle) in a cyclic manner. E.g. you propagate a horizontal line from the point <code>X</code> down until there is a obstacle along that line, then you propagate a vertical line left until you encounter an obstacle, then a horizontal line up and a vertical line right. You repeat this starting at with one of the four moving lines to get four rectangles, and then you select the rectangle with the largest area. However, I do not know if this is optimal, nor the quickest approach.</p>