3
$\begingroup$

I have a 2D bitmap with various shapes (each pixel is either 1 or 0).

How can I find the largest axis-aligned rectangle that covers only set pixels?

$\endgroup$
7
  • $\begingroup$ What do you mean by largest? In terms of area? $\endgroup$ Dec 3, 2021 at 19:58
  • $\begingroup$ @YuvalFilmus yes, largest area $\endgroup$ Dec 3, 2021 at 19:59
  • $\begingroup$ @PålGD 1D is easy, you can just do it in a single O(n) swipe left to right $\endgroup$ Dec 3, 2021 at 20:00
  • $\begingroup$ Are you ok with an approximation? $\endgroup$ Dec 3, 2021 at 20:04
  • 1
    $\begingroup$ You can in linear time compute the number of zeros in the rectangle (0,0) to (i,j). You can use this to query whether (up,left),(down,right) defines a valid rectangle in constant time. $\endgroup$
    – Pål GD
    Dec 3, 2021 at 20:15

1 Answer 1

1
$\begingroup$

It can be done in $O(n^3)$ time, for a $n\times n$ bitmap.

Let $A$ denote the image, so $A[i,j]$ is the pixel at coordinates $(i,j)$.

For each pixel $(i,j)$, let $H[i,j]$ denote the height of the column of all-1 pixels below it, i.e., the largest $h$ such that $A[i',j]=1$ for all $i' \in [i,i+h-1]$.

For each pixel $(i,j)$ and each height $h$, let $W[i,j,h]$ denote the width of the rectangle of height $h$ with upper-left corner at $(i,j)$ that has covers only set pixels, i.e., the largest $w$ such that $H[i,j'] \ge h$ for all $j' \in [j,j+w-1]$.

You can compute each element of $H$ in $O(1)$ time using dynamic programming (fill them in from the bottom up). Also, once you have $H$, you can compute each element of $W$ in $O(1)$ time using dynamic programming (fill them in the right to left).

Finally, once you have $W$, it is trivial to find the largest rectangle, by scanning all of its elements.

In other words, if you have a $n\times n$ bitmap, you can fill in $H$ in $O(n^2)$ time and fill in $W$ in $O(n^3)$ time, and then you can find the largest rectangle in $O(n^3)$ time. So, this gives an $O(n^3)$ time algorithm. That is an improvement over Pål GD's algorithm, which takes $O(n^4)$ time.

If the bitmap is rectangular rather than square, you can use the same algorithm. I suggest you transpose it first if it is taller than it is wide; that way you will have fewer values of $h$ to iterate over. In this way, if you have a $m\times n$ bitmap, the running time will be $O(\min(mn^2,m^2n))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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