Finding rectangles in a 2d block grid

by

Call the width and height of the input array W and H respectively.

  1. Run this clever O(WH) algorithm for determining the largest rectangle, but instead of tracking just the single largest rectangle, for each (x, y) location record in a W*H matrix the width and height of (one or all of) the largest rectangles whose top-left corner is (x, y), updating these values as you go.
  2. Loop through this matrix, adding each sufficiently-large rectangle in it to a max-heap ordered by area (width * height).
  3. Read entries out of this heap; they will be produced in decreasing area order. With every entry read whose top-left corner is (x, y) and which has width w and height h, mark each of the wh locations included in the rectangle as “used” in a WH bit array. When reading rectangles from the heap, we must discard any rectangles that contain “used” squares to avoid producing overlapping rectangles. It’s sufficient to check just the four edges of each candidate rectangle against the “used” array, since the only other way that the candidate rectangle could overlap another rectangle would be if the latter rectangle was completely contained by it, which is impossible due to the fact that we are reading rectangles in decreasing area order.

This approach is “greedy” insofar as it won’t guarantee to choose the largest sequence of rectangles overall if there are multiple ways to carve a solid coloured region into maximal rectangles. (E.g. it might be that there are several rectangles whose top-left corner is at (10, 10) and which have an area of 16: 16×1, 8×2, 4×4, 2×8, 1×16. In this case one choice might produce bigger rectangles “downstream” but my algorithm doesn’t guarantee to make that choice.) If necessary you could find this overall optimal series of rectangles using backtracking, though I suspect this could be very slow in the worst case.

The maximum-rectangle algorithm I mention is designed for single-colour rectangles, but if you can’t adapt it to your multi-colour problem you can simply run it once for each colour before starting step 2.

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. How do I create a URL shortener? [closed]
  3. Segmented Sieve of Eratosthenes?
  4. How do I calculate a point on a circle’s circumference?
  5. Algorithm for Additive Color Mixing for RGB Values
  6. Algorithm to generate all possible permutations of a list?
  7. Fast permutation -> number -> permutation mapping algorithms
  8. Algorithm to detect intersection of two rectangles?
  9. An efficient compression algorithm for short text strings [closed]
  10. Generating the partitions of a number
  11. How to detect the BPM of a song in php [closed]
  12. Find the shortest path in a graph which visits certain nodes
  13. Algorithm to separate items of the same type
  14. how to calculate binary search complexity
  15. What’s a good algorithm to generate a maze? [closed]
  16. Array remove duplicate elements
  17. What string similarity algorithms are there?
  18. Combined area of overlapping circles
  19. Unsupervised clustering with unknown number of clusters
  20. What is the fastest way to find the closest point to a given point?
  21. Quick Sort Vs Merge Sort [duplicate]
  22. Algorithm to find the maximum sum in a sequence of overlapping intervals
  23. Iterating over a Binary Tree with O(1) Auxiliary Space
  24. Big-oh vs big-theta [duplicate]
  25. Peak detection of measured signal
  26. Find prime numbers using Scala. Help me to improve
  27. Difference between average case and amortized analysis
  28. Reservoir sampling
  29. How do I find the position of matching parentheses or braces in a given piece of text?
  30. how to determine if the kth largest element of the heap is greater than x

Leave a Comment