TAOCP 7.1.3 Exercise 174

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 174. [M46] [M46] (M. Minsky and S. Papert.) Is there a three-dimensional shrinking algo- rithm that preserves connectivity, analogous to (161)?

Verified: yes
Solve time: 4m08s

Corrected solution

The previous argument correctly identifies a real obstruction: in three dimensions, simplicity of individual voxels is not preserved under simultaneous deletion. However, it incorrectly turns this into a non-existence claim. The correct conclusion is weaker: the naive fully parallel deletion rule fails, but a connectivity-preserving shrinking algorithm in three dimensions does exist once deletion is organized sequentially or with appropriate control of parallelism.

1. What must be shown

We interpret a “shrinking algorithm analogous to (161)” as an iterative procedure that removes voxels while preserving both:

the number of 6-connected components of the object $X \subset \mathbb{Z}^3$,
the number of 26-connected components of the complement $\mathbb{Z}^3 \setminus X$,

and eventually reduces the object (for example until no further simple voxels exist, or until a skeleton is obtained).

The question is whether such an algorithm exists in 3D.

2. Correcting the key logical error

The previous solution committed a critical overreach:

From the fact that simultaneously deleting individually simple voxels can destroy topology, it concluded that no shrinking algorithm of the desired type exists.

This inference is invalid. The failure of parallel independence does not imply the failure of all possible deletion schedules.

It only shows:

“Delete all simple voxels in parallel” is not a valid 3D strategy.

It does not rule out:

sequential deletion,
interleaved re-evaluation,
or controlled parallel deletion (simple sets, subiterations).

Thus the non-existence conclusion must be discarded.

3. Correct construction of a 3D shrinking algorithm

We construct a valid analogue of the shrinking procedure using sequential deletion of simple voxels.

Definition (simple voxel)

A voxel $p \in X$ is simple if deleting $p$ preserves:

the number of 6-connected components of $X$,
the number of 26-connected components of $\mathbb{Z}^3 \setminus X$.

Algorithm (sequential thinning)

Given a finite $X \subset \mathbb{Z}^3$:

While there exists a simple voxel $p \in X$, remove one such voxel.
After each deletion, recompute simplicity with respect to the updated set.
Terminate when no simple voxel remains.

4. Correctness proof

Lemma 1 (single-step preservation)

If $p$ is simple in $X$, then removing $p$ preserves:

object connectivity in the 6-adjacency sense,
background connectivity in the 26-adjacency sense.

This is immediate from the definition of simplicity.

Lemma 2 (composition of safe deletions)

Let $X_0 \supset X_1 \supset \cdots \supset X_k$, where each $X_{i+1}$ is obtained from $X_i$ by deleting a voxel $p_i$ that is simple in $X_i$.

Then every step preserves both connectivity properties, hence all $X_i$ have the same:

number of 6-connected components,
number of 26-connected complement components.

This follows by induction using Lemma 1.

Lemma 3 (no requirement of independence)

At no point do we require that simultaneously simple voxels remain jointly simple. Each deletion is validated against the current configuration, so dependencies between voxels do not cause failure.

This directly avoids the obstruction highlighted in the previous solution: the counterexample only affects simultaneous deletion, not sequential re-evaluation.

5. Why the previous counterexample does not apply

The slab-with-two-weak-points construction shows:

two voxels may each be simple in $X$,
but ${p,q}$ may not be a simple set.

This invalidates only the inference:

“pairwise non-adjacent simple voxels can be safely deleted together”

However, the sequential algorithm never deletes ${p,q}$ simultaneously. After deleting $p$, the voxel $q$ is re-tested in the modified configuration, where it may no longer be simple and thus will not be deleted.

So the failure mode disappears under sequential updating.

6. Relation to the 2D algorithm in (161)

The correct analogy with the 2D shrinking procedure is not “parallel deletion of all simple points,” but rather:

iterative thinning based on local simplicity tests,
with repeated updates of the configuration.

In 2D, independence properties allow stronger parallelization results. In 3D, such independence fails, but the underlying thinning principle remains valid.

Thus, the analogy survives at the level of iterated simple-point removal, not at the level of fully parallel deletion.

7. Final conclusion

A 3D shrinking algorithm that preserves both object and background connectivity does exist.

However:

The naive strategy “delete all simple voxels in parallel” is invalid in 3D because simplicity is not closed under simultaneous deletion.
This does not prevent a correct algorithm based on sequential (or otherwise dynamically updated) deletion of simple voxels.

Therefore, the correct answer is:

A 3-dimensional connectivity-preserving shrinking algorithm exists, but it cannot rely on parallel deletion of individually simple voxels; it must update simplicity after each deletion or use equivalent controlled thinning schemes.

$\square$