2

We have a rectangular grid with size NxM, in which each cell can be either free or occupied. Number or free cells is much bigger than number of occupied, thus we represent our grid as a list of XY coordinates of occupied cells. Also we assume that occupied cells have a certain structure.

We want to find a largest rectangle which covers only free cells. Next we want to find another largest rectangle which should not only cover only free cells, but also which should not overlap with previously found rectangles. We want to find all such rectangles up to a given threshold area.

In other words we want to find a rectangular tiling which covers maximum area of free cells using greedy algorithm.

Example:

Input grid (0 - free, x - occupied):

0 0 0 0 0
0 0 0 0 0
x 0 x 0 0
0 0 x 0 0
0 0 0 0 0

Solution (cell numbers denote solution rectangles):

1 1 1 1 1
1 1 1 1 1
x 0 x 2 2
3 3 x 2 2
3 3 0 2 2

What algorithms can be used to computationally effectively solve this problem? On a first glance some kind of index (e.g. quadtree) should be utilized to get a practical performance for large M and N (e.g. hundreds of thousands). Solution does not have to be optimal, sub-optimal, but computationally efficient approaches, are good as well. Academic literature references are welcomed!

Bonus points: generalized approach applicable to 2D and 3D grids (and maybe even to higher dimensions as well).

user3234005
  • 342
  • 1
  • 2
  • 10
  • The optimal 1 step solution seems to be [this](https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/). Would need a better approach than running same algorithm till thereshold is met – juvian Apr 08 '19 at 15:45
  • SO is not really a "code this for me" site, so you better should show us your efforts and the problems you've run into, then we can start helping you solve these problems instead of doing all the work for you ;-) – Alfe Apr 08 '19 at 15:49
  • @juvian I am familiar with the linked algorithm, but it has quadratic difficulty not only in time, but also in memory, while I've hoped for something with logarithm in it. – user3234005 Apr 08 '19 at 15:51
  • Like O(n² × log n) ;-D – Alfe Apr 08 '19 at 15:52
  • 1
    Would a non-perfect approach also be applicable to your case? I guess the problem is a hard one and finding the optimal solution won't be possible below O(n²). But something like an approximation might be way faster possible. – Alfe Apr 08 '19 at 15:53
  • 1
    Yes, I forgot to mention it, sub-optimal solutions are good as well. – user3234005 Apr 08 '19 at 15:54
  • My first approach would be: Take a random position (seed). Grow a rectangle from that seed to maximum possible width. Grow it from there to maximum possible height, then shrink it again horizontally in order to allow it to grow vertically again. This way you will get a list of possible rectangles for this seed. Do this for several seeds and take the largest. Then repeat this process. Finding such a maximum should be O(k) with _k_ being the number of already occupied rectangles (probably way lower than _n_ and _m_ of your _n×m_ grid). So I guess you would get O(k×q) (_q_ = #rect to be found). – Alfe Apr 08 '19 at 16:01
  • What if the grid doesn't contain `x`?. What if started `x` on aligned with ended `x`? Is that all cases, you sure? – Ibrahim Ali Apr 08 '19 at 17:06
  • If you have few occupied, you might want to iterate those and check the largest rectangle you can make with its free neighbours (any free largest rectangle has at least 1 occupied cell as neightbour). I don´t know how to check that efficiently though – juvian Apr 08 '19 at 17:12
  • To clarify, are you asking whether you can do better in time and/or space than looking at each of the n^2 x m (or fewer) possible rectangles and seeing which is the biggest unoccupied one? – Patrick87 Apr 08 '19 at 20:54
  • We can binary search valid rectangles given a fixed corner. Matrix prefix sums can tell us if it includes an occupied cell in O(1) provided the space with any occupied cells is small enough to support such a matrix. If not, I'm sure there are some multi-dimensional trees that would support finding if the rectangle includes an occupied cell in better than linear time. – גלעד ברקן Apr 08 '19 at 22:19
  • This problem is called splitting of rectilinear polygon (or something similar :-). Check this question https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles-without – Ante Apr 11 '19 at 13:45

0 Answers0