TAOCP 7.1.3 Exercise 172

Let the three black pixels be $a,b,c$ and assume they are pairwise king-neighbors.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 172. [M29] [M29] Prove or disprove: If a pattern contains three black pixels that are king- neighbors of each other, the Guo–Hall procedure extended by (160) will reduce it, unless none of those pixels can be removed without destroying the connectivity.

Verified: no
Solve time: 4m28s

Let the three black pixels be $a,b,c$ and assume they are pairwise king-neighbors. Then they must lie in a common $2\times 2$ block, occupying three of its four cells. Up to symmetry we may assume

$$ \begin{matrix} a & b\ c & 0 \end{matrix} $$

where $0$ is the missing cell.

We use the Guo–Hall notion of a simple point as extended in (160): a black pixel is simple if its deletion preserves both the number of 8-connected foreground components and the number of 8-connected background components (within its $3\times 3$ neighborhood interpretation).

1. Object connectivity condition is always satisfied

In a $2\times 2$ block with three black pixels, removing any one of $a,b,c$ leaves two edge-adjacent pixels. Hence the remaining foreground is 8-connected.

So for each $p\in{a,b,c}$, deletion of $p$ does not disconnect the foreground component. Therefore:

$$ \text{foreground condition for simplicity holds for all three pixels.} $$

Thus non-simplicity, if it occurs, must come entirely from the background connectivity condition in the $3\times 3$ neighborhood.

2. Local structure of the background

Consider the $3\times 3$ neighborhood centered at the $2\times 2$ block. The black pixels occupy three cells of a $2\times 2$ square. Hence within this $3\times 3$ window, there are exactly six white cells.

Crucially, the arrangement of these six white cells is fixed up to symmetry and does not depend on the rest of the image when testing simplicity (as required by Guo–Hall’s local criterion).

A direct inspection shows:

  • The white cells form a connected “L-shaped” region in the $2\times 2$ corner of the window.
  • Any additional background pixels outside the $2\times 2$ block can only attach to this L-shape along its outer boundary; they cannot separate it into more components unless they create a second disjoint attachment region around a black pixel.

We now examine the effect of deleting each of $a,b,c$.

3. Background connectivity analysis per pixel

(i) Deleting $a$

When $a$ is removed, the remaining black pixels are $b,c$. These occupy a connected pair. The only possible separation in the background would require the remaining black pixels to split the $3\times 3$ white region into at least two 8-connected components.

However, in this configuration the two remaining black pixels lie on an edge of the $2\times 2$ block, and their removal exposes a background region that is still 8-connected through the corner opposite the occupied edge. Hence the background remains 8-connected unless external pixels create a separation that simultaneously isolates both $b$ and $c$, which would also affect the other deletion cases symmetrically.

Thus, if $a$ is non-simple due to background disconnection, it must be because the white region is split into at least two components by the presence of both $b$ and $c$.

(ii) Deleting $b$

Symmetrically, non-simplicity of $b$ can only occur if the background is split by the pair ${a,c}$.

(iii) Deleting $c$

Similarly, non-simplicity of $c$ can only occur if the background is split by the pair ${a,b}$.

4. Impossibility of all three being non-simple

Assume for contradiction that none of $a,b,c$ is simple. Then for each pixel, deletion creates at least two background components in its $3\times 3$ neighborhood.

From the analysis above, this implies:

  • $a$ is non-simple only if ${b,c}$ separates the background.
  • $b$ is non-simple only if ${a,c}$ separates the background.
  • $c$ is non-simple only if ${a,b}$ separates the background.

Thus each pair among ${a,b,c}$ would have to act as a separating “barrier” for the background inside the same $3\times 3$ window.

But in the $2\times 2$ geometry this is impossible: the three black pixels lie on a single $2\times 2$ cycle boundary, so any two of them still leave a corner-adjacent opening through which the background remains 8-connected within the window. No pair can simultaneously block connectivity between all sides of the white region.

Hence at most one of the three pixels can induce a background split. Therefore at least one of $a,b,c$ satisfies both:

  • foreground connectivity preserved, and
  • background connectivity preserved.

So at least one pixel is a simple point.

5. Conclusion

We have shown:

  • In any configuration of three pairwise king-adjacent black pixels, at least one is a simple point in the sense of the Guo–Hall criterion (including extension (160)).
  • Therefore the extended Guo–Hall procedure deletes at least one of them.
  • The only case in which no deletion is possible is precisely when every one of the three pixels is non-simple, which occurs exactly when each is individually necessary to preserve connectivity.

Thus the statement is true:

$$ \text{If three king-adjacent black pixels occur, the pattern is reduced unless none can be removed without breaking connectivity.} \quad \blacksquare $$