TAOCP 7.1.3 Exercise 183

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 183. ▶ [M29] [M29] (G. Rote.) Explain why Algorithm T might fail if condition (v) is false.

Verified: yes
Solve time: 3m11s

Let $F(x,y)$ be the integer-valued function defining the conic, as in Algorithm T. The algorithm traces a grid path by moving from a lattice point to one of two candidates, say $E:(x+1,y)$ or $N:(x,y+1)$, using only local evaluations of $F$ at finitely many nearby points.

Condition (v) in Knuth’s construction is the local uniqueness condition: in every unit square of the grid, the sign information of $F$ at the finitely many points inspected by the algorithm determines a unique correct continuation of the digitized curve. Equivalently, whenever the curve enters a unit square, the pattern of signs on the relevant test points guarantees that exactly one of the two possible successor moves corresponds to the edge of the square through which the conic actually leaves. This excludes ambiguous configurations in which the same local data are compatible with two different exits of the curve from the cell.

Assume now that condition (v) is false. Then there exists a unit square $S$ and two distinct geometric continuations of the conic through $S$ that produce the same values of all quantities used by Algorithm T in its decision step (the evaluated values of $F$ at the prescribed nearby lattice points or linear combinations thereof). In particular, the local data do not determine a unique exit edge of the curve from $S$.

There are two cases.

First, the conic intersects $S$ in such a way that it crosses two different edges of $S$ in a manner consistent with the same sign pattern at all test points. Then both candidate moves from the current lattice point (for example $E$ and $N$, or their symmetric alternatives depending on the entry edge) are locally admissible according to the decision rule. Since Algorithm T has no access to global information, it must choose one of them arbitrarily according to its fixed rule. Whichever choice is made, it will disagree with the true exit edge in at least one realization of the same local configuration, so the produced lattice path deviates from the boundary of the conic.

Second, the conic may pass through $S$ in a configuration where the entry and exit edges are not uniquely determined by the sign pattern (a degenerate or nearly tangential crossing). In this situation the incremental update used by Algorithm T for its decision variable, which assumes that the ordering of sign changes along candidate moves is consistent, no longer corresponds to the actual variation of $F$ across the square. As a result, the algorithm may either advance to a point that the curve does not reach from the previous step, creating a gap, or may select a move that forces a second crossing of the same cell boundary, producing an overlap.

In both cases the essential invariant of Algorithm T fails: that at each step the chosen move follows the unique edge of the unit square through which the conic passes. When condition (v) is false, this uniqueness is lost, while the algorithm still bases its decision solely on local evaluations. Hence the local predicate computed by Algorithm T is no longer sufficient to determine the correct continuation of the curve, and the algorithm can produce a path that diverges from the true digitization of the conic. ∎