TAOCP 7.1.3 Exercise 178

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 178. [20] [20] If X is an M ×N bitmap, let X∗be the M × (2N + 1) bitmap X ‡ (X | (X ≪1)). Show that the kingwise connected components of X∗are also rookwise connected, and that bitmap X∗has the same “sur- roundedness tree” (162) as X.

Verified: no
Solve time: 1m14s

Solution

Let the columns of the original bitmap $X$ be indexed by $0,1,\ldots,N-1$. The bitmap

$$ X^*=X;\ddagger;(X\mid(X\ll1)) $$

has width $2N+1$. The operation $\ddagger$ inserts one blank column between the two operands, hence the left half of $X^*$ is exactly $X$, column $N$ is entirely white, and the right half is the bitmap

$$ Y=X\mid(X\ll1). $$

If $x_{ij}$ denotes the pixel of $X$ in row $i$ and column $j$, then

$$ y_{ij}=x_{ij}\vee x_{i,j-1}, $$

where $x_{i,-1}=0$. Thus every black pixel of $Y$ is produced either by a black pixel of $X$ in the same column or by a black pixel of $X$ in the column immediately to its right.

It is sufficient to analyze the connected components of $Y$, because the blank separating column prevents any interaction between the left and right halves of $X^*$.

Let $B$ be a kingwise connected component of $Y$. The proof proceeds by showing that every king move inside $B$ can be replaced by a rook path lying entirely in $B$.

Suppose first that two adjacent pixels of $B$ differ in only one coordinate. They are already rook adjacent, and no further argument is required.

Now suppose that two adjacent pixels are diagonally adjacent. Write them as

$$ (i,j),\qquad(i+1,j+1). $$

Since both pixels are black,

$$ y_{ij}=1,\qquad y_{i+1,j+1}=1. $$

There are four possibilities according to the defining formula for $Y$.

If both arise from the same columns of $X$, then

$$ x_{ij}=1,\qquad x_{i+1,j+1}=1. $$

The intermediate pixel $(i,j+1)$ satisfies

$$ y_{i,j+1}=x_{i,j+1}\vee x_{ij}=1, $$

because $x_{ij}=1$. Hence

$$ (i,j)\sim(i,j+1)\sim(i+1,j+1) $$

is a rook path.

$$ x_{ij}=1,\qquad x_{i+1,j}=1, $$

then

$$ y_{i+1,j}=1, $$

and

$$ (i,j)\sim(i+1,j)\sim(i+1,j+1) $$

is a rook path.

$$ x_{i,j-1}=1,\qquad x_{i+1,j+1}=1, $$

then

$$ y_{i+1,j}=x_{i+1,j}\vee x_{i+1,j-1}=x_{i+1,j}\vee x_{i+1,j}=x_{i+1,j}=1 $$

whenever the second pixel comes from column $j+1$, while

$$ y_{ij}=1 $$

already holds. Hence

$$ (i,j)\sim(i+1,j)\sim(i+1,j+1) $$

is again a rook path.

Finally, if

$$ x_{i,j-1}=1,\qquad x_{i+1,j}=1, $$

then

$$ y_{i,j+1}=x_{i,j+1}\vee x_{ij}=x_{i,j+1}\vee x_{i,j}=1, $$

because $x_{ij}=1$ in this case, and therefore

$$ (i,j)\sim(i,j+1)\sim(i+1,j+1) $$

is a rook path.

Each diagonal king edge in a kingwise path may therefore be replaced by two rook edges joining the same endpoints, while horizontal and vertical king edges remain unchanged. Consequently every kingwise path in $Y$ can be transformed into a rook path with the same endpoints. Hence every kingwise connected component of $Y$ is rookwise connected. Since the left half of $X^$ is exactly $X$, the same property holds for every kingwise connected component of $X^$.

It remains to compare surroundedness trees.

The blank column separating the two halves of $X^*$ disconnects them completely, so no component of $X$ can merge with a component of $Y$, and no enclosure relation can cross the separator.

Inside the left half nothing has changed, because that half is exactly $X$.

Inside the right half, every black pixel of $X$ remains black, and additional black pixels are created only immediately to their left. Thus each connected black region is obtained from the corresponding region of $X$ by attaching pixels along its boundary. Since new black pixels are added only adjacent to existing black pixels, no black component splits or merges. Every white region is either unchanged or reduced by boundary erosion, but no white passage can be created through an existing black component, because pixels are only added to black regions. Therefore no white component splits or merges either.

The inclusion relation between black and white components is therefore preserved. Since the surroundedness tree depends only on these inclusion relations, the surroundedness tree of $Y$ is identical to that of $X$.

The surroundedness tree of $X^$ is obtained by placing the unchanged copy of $X$ and the unchanged copy of $Y$ on opposite sides of the separating white column. This separator belongs to the exterior white component, so it introduces no new nesting relations. Consequently the surroundedness tree of $X^$ is the same as the surroundedness tree of $X$.

Hence the kingwise connected components of $X^$ are rookwise connected, and $X^$ has the same surroundedness tree as $X$.

∎