Problem

Given an occupancy grid, for example:

...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....

Where, * represents an occupied block, . represents a free block and X represents a point (or block) of interest, what is the most time-efficient algorithm to find the largest rectangle which includes X, but does not include any obstacles, i.e. any *?

For example, the solution to the provided grid would be:

.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....

My Thoughts

Given we have a known starting point X, I can't help but think there must be a straightforwards solution to "snap" lines to the outer boundaries to create the largest rectangle.

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 X 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.