TAOCP 7.1.3 Exercise 164
Let the eight neighbors of a cell $X$ be $X_{NW}, X_N, X_{NE}, X_W, X_E, X_{SW}, X_S, X_{SE}$.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 164. [23] [23] The original definition of custerization in 1957 was not (157) but custer′(X) = X & ∼(XNW & XN & XNE & XW & XE & XSW & XS & XSE). Why is (157) preferable?
7.1.3 BITWISE TRICKS AND TECHNIQUES 197
Verified: yes
Solve time: 2m26s
Let the eight neighbors of a cell $X$ be $X_{NW}, X_N, X_{NE}, X_W, X_E, X_{SW}, X_S, X_{SE}$.
The two definitions are
$$ custer'(X)= X ,&, \neg(X_{NW},&,X_N,&,X_{NE},&,X_W,&,X_E,&,X_{SW},&,X_S,&,X_{SE}) $$
and
$$ custer(X)= X ,&, \neg(X_{NW},\vee,X_N,\vee,X_{NE},\vee,X_W,\vee,X_E,\vee,X_{SW},\vee,X_S,\vee,X_{SE}). $$
1. Rewriting both operations in set-theoretic form
Let
$$ N(X) = X_{NW},\vee,X_N,\vee,X_{NE},\vee,X_W,\vee,X_E,\vee,X_{SW},\vee,X_S,\vee,X_{SE} $$
be the set of all points having at least one 8-neighbor in $X$.
Then (157) becomes
$$ custer(X) = X \setminus N(X). $$
Thus a point of $X$ is removed exactly when it has at least one neighbor in $X$.
For the modified definition, define
$$ M(X) = X_{NW},&,X_N,&,X_{NE},&,X_W,&,X_E,&,X_{SW},&,X_S,&,X_{SE}. $$
Then
$$ custer'(X) = X \setminus M(X), $$
so a point is removed only when all eight neighboring positions are simultaneously in $X$.
2. Logical nature of the two conditions
The key difference is the quantifier structure over the neighborhood:
- (157) uses an existential condition:
$$ \exists,Y \in \text{neighbors of }X \text{ such that } Y \in X. $$
Equivalently, a point is affected whenever it has any neighbor in $X$.
- The modified version uses a universal condition:
$$ \forall,Y \in \text{neighbors of }X,; Y \in X. $$
It triggers only in the extreme case where the entire neighborhood is filled.
3. Why (157) is preferable
The intended notion of “custerization” is a local geometric operation that reacts to adjacency in a robust way. For such operations, the natural and stable primitive is the existence of a neighbor, not the simultaneous presence of all neighbors.
(a) Correct notion of local interaction
In a grid, connectivity and clustering are defined through adjacency: a point is considered part of a structure precisely when it touches other points. This is inherently an existential property.
Therefore, the appropriate predicate is:
$$ \text{“has a neighbor in }X\text{”} $$
which is exactly what the OR expression encodes.
(b) Why the AND-based version is inappropriate
The modified condition requires all eight neighbors to be present. This is a universal constraint on the entire neighborhood, not a locality test.
This is too strong for detecting geometric structure:
- It ignores most configurations where a point is clearly internal or boundary-like.
- It only reacts in the degenerate case of a fully occupied 8-neighborhood.
- Small perturbations of the neighborhood (removing one neighbor) completely change the outcome, making the rule overly brittle.
Thus it does not correspond to any meaningful notion of adjacency or clustering.
(c) Structural reason: union vs intersection of shifts
The OR-form expression corresponds to a union of shifted copies of $X$, which is the standard way neighborhood-based operators are defined. It yields a shift-invariant local operator based on aggregation over directions.
The AND-form corresponds to an intersection of all shifted copies, which is not aligned with neighborhood detection and produces a condition unrelated to boundary or connectivity.
4. Conclusion
Expression (157) is preferable because it encodes an existential neighborhood condition (“at least one neighbor”), which is the correct primitive for local geometric and connectivity-based operations on a grid.
The alternative definition replaces this with a universal condition (“all neighbors”), which is overly restrictive, ignores the intended notion of adjacency, and does not produce a meaningful or stable clustering operator.