Find the rectangle with the maximum area, containing a specific point in an occupancy grid

4
votes

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.

2
algorithmcomplexity-theorycomputational-geometry
@MrSmith42 yes, apologies it should be. I have edited the question – Athena
whts the complexity of your proposed solution? – Serial Lazer
If we have R rows and C columns, likely to be O(R*C), that being said however, I don't believe my approach will find an optimal solution. – Athena
I dont think there's any solution more optimal than O(R*C), worst case being: X at bottom-right cell and the biggest-block being the whole rectangle – Serial Lazer
The largest rectangle that includes X is the entire field. If you have further constraints, state them explicitly in the question. – Mo B.

2 Answers

4
votes

This problem is a well-known one in Computational Geometry. A simplified version of this problem (without a query point) is briefly described here. The problem with query point can be formulated in the following way:

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.

The paragraph above has been copied from this paper, where authors describe an algorithm and data structure for the set with N points in the plane, which allow to find a maximal empty rectangle for any query point in O(log^4(N)) time. Sorry to say, it's a theoretic paper, which doesn't contain any algorithm implementation details.

2
votes

A possible approach could be to somehow (implicitly) rule out irrelevant occupied cells: those that are in the "shadow" of others with respect to the starting point:

 0         1          X
 01234567890123456789 →
0....................
1....................
2...*................
3...........*........
4....................
5..*.......X.........
6............*.......
7....*...............
8....................
9....................

↓ Y

Looking at this picture, you could state that

  • there are only 3 relevant xmin values for the rectangle: [3,4,5], each having an associated ymin and ymax, respectively [(3,6),(0,6),(0,9)]
  • there are only 3 relevant xmax values for the rectangle: [10,11,19], each having an associated ymin and ymax, respectively [(0,9),(4,9),(4,5)]

So the problem can be reduced to finding the rectangle with the highest area out of the 3x3 set of unique combinations of xmin and xmax values

If you take into account the preparation part of selecting relevant occupied cells, this has the complexity of O(occ_count), not taking into sorting if this would still be needed and with occ_count being the number of occupied cells.

Finding the best solution (in this case 3x3 combinations) would be O(min(C,R,occ_count)²). The min(C,R) includes that you could choose the 'transpose' the approach in case R<C, (which is actually true in this example) and that that the number of relevant xmins and xmaxs have the number of occupied cells as an upper limit.