3
$\begingroup$

Take an image, (the Google home page) is a good example.

I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.

Do you know any algorithms that would do this?

$\endgroup$
2
$\begingroup$

Subtract $254.9999999$ from all pixel values, so black corresponds to $-254.9999999$ and white to $0.0000001$.

Find the 2D subrectangle with maximum sum. There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/). As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).

Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.

$\endgroup$
3
  • $\begingroup$ Surely the subrectangle with maximum sum would be a single pixel? $\endgroup$
    – zooby
    Apr 1 '20 at 19:12
  • $\begingroup$ @zooby, no, a subrectangle with two white pixels sums to 0.0000002, while a subrectangle with one white pixel sums to 0.0000001; the former is larger. In general, only all-white subrectangles have a positive sum; and the larger the all-white subrectangle, the larger its sum. $\endgroup$
    – D.W.
    Apr 1 '20 at 19:20
  • $\begingroup$ Oh right I thought there was a minus sign. $\endgroup$
    – zooby
    Apr 1 '20 at 19:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.