TAOCP 7.1.3 Exercise 179

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 179. ▶ [34] [34] Design an algorithm that constructs the surroundedness tree of a given M × N bitmap, scanning the image one row at a time as discussed in the text. (See (162) and (163).)

Verified: no
Solve time: 4m20s

The failure in the proposed solution is not a technical detail. It is a structural mistake: it tries to recover a topological nesting relation (surroundedness) from a purely graph-theoretic shortest-path construction. That cannot work in general planar region adjacency graphs.

The fix is to stop using the region adjacency graph as the primary object for inference and instead reconstruct the planar subdivision induced by the bitmap, then derive inclusion from that planar structure.

The key idea is:

A surroundedness tree is the containment tree of faces in a planar subdivision, not a BFS tree in an adjacency graph.

1. What must be computed

The bitmap induces a partition of the plane into maximal monochromatic connected regions. The surroundedness tree is defined on these regions by:

A region $A$ is the parent of region $B$ if $A$ is the smallest region that strictly contains $B$ in the plane.

This is a geometric containment relation, not a graph distance relation.

The correct construction must therefore recover planar nesting.

2. Correct high-level strategy

We separate the problem into three independent stages:

Compute connected components (scanline + union–find).
Extract the planar boundary structure between components.
Compute face containment using winding structure, then build the inclusion tree.

The key correction is that step 3 uses planar geometry, not BFS.

3. Step 1: connected components (unchanged, correct)

Scan the bitmap row by row.

Represent each maximal monochromatic run as a node.
Use union–find to merge horizontally and vertically adjacent runs of the same color.

After the scan we obtain the set of components:

$$ \mathcal{C}_W \cup \mathcal{C}_B. $$

This part is correct and unchanged.

We also record all adjacency between opposite-colored runs, but this is now only used to reconstruct boundaries, not to compute nesting.

4. Step 2: reconstruct boundary edges

From scanline adjacency, build the set of boundary edges:

Each time a white run touches a black run, we record the interface segment between them as a directed edge in a planar graph embedding.

This yields a planar subdivision graph $G_\partial$ whose edges lie on pixel grid boundaries.

Important correction:

We do not build a region adjacency graph.
We build the geometric boundary graph of the partition.

Each edge has an embedding in the plane.

5. Step 3: extract closed boundary cycles (faces)

The boundary graph $G_\partial$ decomposes into Eulerian cycles.

We traverse it to extract all maximal simple cycles. Each cycle corresponds to a face boundary in the planar subdivision.

This is standard planar graph decomposition:

Each edge belongs to exactly two directed boundary traversals.
Following the “keep face on the left” rule yields all cycles.

This produces a set of faces:

$$ \mathcal{F} = {F_0, F_1, \dots}, $$

where one is the exterior face.

Crucial correction:

These faces are the correct objects of nesting. Not the connected components alone.

6. Step 4: compute face containment depth

Now we assign each face a nesting depth using a correct planar invariant.

Pick a point in each face (for example the lexicographically smallest pixel strictly inside the face).

Compute the winding parity with respect to all boundary cycles using a horizontal ray:

For a point $p$, cast a ray to infinity.
Count signed crossings of boundary edges.

Define:

$$ \operatorname{depth}(F) = \text{number of enclosing boundary cycles containing } F. $$

This is well-defined because in a planar subdivision:

each crossing flips inside/outside status,
nesting depth is invariant under choice of ray,
and does not depend on adjacency distance.

This replaces the incorrect BFS distance.

7. Step 5: build inclusion tree correctly

We now define the parent relation geometrically.

For any face $F \neq F_{\text{ext}}$, define:

$$ \operatorname{parent}(F) = \text{the unique face } G \text{ such that} $$

$G$ strictly contains $F$,
$\operatorname{depth}(G) = \operatorname{depth}(F) - 1$,
and there is no intermediate face strictly between them.

Uniqueness follows from planar nesting: depth levels form a hierarchy induced by nested Jordan curves.

Thus the faces form a rooted tree with root $F_{\text{ext}}$.

This is the surroundedness tree.

8. Why the rejected BFS approach fails (precisely addressed)

Error 1: BFS does not encode geometric containment

Correct. BFS measures combinatorial adjacency distance in a dual graph. Nesting is not preserved by shortest paths.

Two regions may be geometrically far apart but graph-close through alternating components.

Thus BFS layers are meaningless for inclusion.

Error 2: no unique “first separating component”

Correct. Separating structures in planar graphs are not unique. Multiple disjoint barriers can exist, and shortest paths do not define canonical separators.

Only geometric cycles define separation, not adjacency chains.

Error 3: BFS parent ambiguity

Correct. BFS trees are arbitrary spanning trees. Multiple predecessors may exist and tie-breaking destroys geometric meaning.

Containment requires uniqueness derived from planar nesting, not traversal order.

Error 4: planarity does not imply a tree in adjacency graph

Correct. The region adjacency graph is generally cyclic. Cycles are normal and unrelated to containment hierarchy.

The tree arises only after passing to faces and nesting depth.

Error 5: adjacency ≠ containment

Correct and fundamental.

Adjacency describes sharing a boundary.

Containment describes enclosure by closed Jordan curves.

These are different relations.

9. Final corrected algorithm (scanline-compatible)

Scan bitmap row by row.
Build runs and union–find components.
Record boundary segments between opposite-colored runs.
Convert boundary segments into planar boundary cycles (face tracing).
Compute face nesting depth using ray-crossing parity.
For each face, assign its parent as the minimal strictly enclosing face of depth minus one.
Output the resulting inclusion tree.

10. Correctness summary

Components are computed correctly via union–find over scanline runs.
Boundary cycles reconstruct the true planar embedding.
Nesting is computed via winding structure, not graph distance.
The inclusion tree is derived from depth-ordered face containment, which is the mathematical definition of surroundedness.
No BFS or adjacency graph reasoning is used to infer topology.

This yields a valid construction of the surroundedness tree consistent with planar topology and scanline input constraints.