TAOCP 7.1.3 Exercise 182
Let F(x,y)=ax^2+bxy+cy^2+dx+ey+g define the conic, and let the algorithm operate on a segment of the curve on which, say, $x$ is strictly increasing (the other case is symmetric).
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 182. [M31] [M31] Why does the three-register method (Algorithm T) digitize correctly?
Verified: no
Solve time: 2m43s
Corrected solution
Let
$$ F(x,y)=ax^2+bxy+cy^2+dx+ey+g $$
define the conic, and let the algorithm operate on a segment of the curve on which, say, $x$ is strictly increasing (the other case is symmetric). Hence the segment intersects each vertical line at most once.
The three-register method maintains the exact value of $F$ and its discrete first differences, so that for every lattice point $(x,y)$,
$$ F(x+1,y)=F(x,y)+\Delta_x F(x,y), \quad F(x,y+1)=F(x,y)+\Delta_y F(x,y), $$
with $\Delta_x F, \Delta_y F$ updated exactly by fixed linear recurrences. This is correct because $F$ is quadratic, hence its first differences are affine functions of $(x,y)$.
The remaining issue is geometric correctness: why the sequence of lattice moves produced by Algorithm T matches the sequence of grid cells visited by the true curve.
1. Geometric structure of one step
Assume the current lattice point is $P=(x,y)$. The algorithm chooses between two candidate next vertices:
$$ P_x=(x+1,y), \quad P_y=(x,y+1). $$
These correspond to two adjacent grid edges of the current cell. The true curve intersects the boundary of the current unit cell in a connected set (since it is an algebraic curve and hence has no oscillation inside a convex cell under monotone restriction). Moreover, because the segment is monotone in $x$, it can cross the left-to-right strip in only one left-to-right progression; it cannot re-enter a previously left-adjacent cell.
Thus, within each step, the curve must exit the current cell through exactly one of the two “forward” edges (east or north depending on orientation after normalization).
2. Key invariant (digitization invariant)
We maintain:
Invariant I. At each step, the current lattice point $P=(x,y)$ is such that the true curve intersects the boundary of the union of the two candidate successor cells, and exactly one of the two candidate edges incident to $P$ contains the next intersection of the curve with the grid.
Equivalently, the curve crosses either the edge segment from $P$ to $P_x$ or the edge segment from $P$ to $P_y$, but not both.
This is the central geometric statement to be justified.
3. Why exactly one outgoing edge is correct
Restrict $F$ to any grid edge segment, for example
$$ E_x = {(x+t,y) : 0 \le t \le 1}, \quad E_y = {(x,y+t) : 0 \le t \le 1}. $$
On each such segment, $F$ becomes a univariate quadratic polynomial in $t$, hence has at most two zeros. However, because the conic segment is monotone in $x$, the restriction of the curve to the current vertical strip is a single connected arc that cannot oscillate back across the same strip boundary. Therefore, within a single cell, the curve can intersect at most one of the two forward edges in the progression direction; otherwise it would force a violation of monotonicity or create two distinct intersections with a line parallel to the $y$-axis inside the strip.
Hence exactly one of the two candidate edges is the exit edge of the curve.
4. Correct meaning of sign information
The previous argument incorrectly equated sign changes at lattice points with edge crossings. The correct statement is instead:
For any edge segment $E$, if $F$ has opposite signs at its endpoints, then by continuity there is at least one intersection of the curve with $E$. Conversely, if the curve intersects $E$ transversely in its interior, then $F$ must take opposite signs at the endpoints unless both endpoints lie on the curve.
Because a quadratic restricted to a line has at most two roots, and because the segment under consideration is monotone (hence excludes multiple oscillatory crossings of the same edge), this intersection is unique in the relevant cases.
Thus sign information is not interpreted globally, but only as a certificate for which of the two candidate edges contains the unique crossing in the current step.
5. Role of the three-register method
The three registers ensure that at both candidate successor points $P_x$ and $P_y$, the values
$$ F(P_x), \quad F(P_y) $$
are computed exactly and incrementally.
Therefore the algorithm can determine the sign of $F$ at the endpoints of both candidate edges without recomputation.
This is sufficient because, under the invariant above, exactly one of the two edges contains the next intersection, and that edge is uniquely determined by which endpoint configuration is consistent with the curve remaining on the correct side of $F=0$ within the current cell.
6. Why the decision rule is correct
Assume the true curve exits the current cell through the edge $E_x$ or $E_y$.
Because $F$ is continuous and the curve is exactly $F=0$, the sign of $F$ at the vertices adjacent to each edge determines whether the curve must cross that edge to remain consistent with continuity of the level set.
The algorithm’s decision rule compares the two candidate updates:
$$ F(x+1,y) \quad \text{versus} \quad F(x,y+1), $$
together with the already known value $F(x,y)$, and selects the move that preserves consistency of the sign configuration with a continuous passage of the level set through the grid.
Since exactly one outgoing edge is compatible with the existence of a continuous arc of $F=0$ in the next cell (by the monotone-exit argument above), the rule selects the correct move.
7. Inductive correctness
Assume the invariant holds at step $k$. Then:
- The curve intersects exactly one outgoing candidate edge of the current cell.
- The three-register method computes exact values of $F$ at both candidate endpoints.
- The decision rule selects the unique edge consistent with continuity of $F=0$ and the monotone progression of the curve.
Thus the algorithm moves to the next lattice point whose cell boundary contains the next intersection of the curve. The invariant is preserved.
By induction, the produced lattice path visits exactly the sequence of cells intersected by the monotone conic segment.
8. Handling degeneracies
If $F$ vanishes at a lattice vertex, this corresponds to the curve passing exactly through a grid corner. Because the conic is algebraic of degree two, such events are isolated. A consistent tie-breaking rule (fixed preference for one edge) preserves correctness without affecting the global monotone ordering of intersections.
Tangential contacts with grid edges also occur only at isolated points; monotonicity ensures they do not create multiple admissible exits from a single cell, so the same selection rule remains valid.
Conclusion
The correctness of Algorithm T follows from three facts:
- The three-register method computes $F$ exactly at all relevant lattice points.
- On a monotone conic segment, each grid cell has exactly one valid exit edge for the curve.
- The decision rule identifies this unique exit edge using exact sign information of $F$ at candidate endpoints.
Therefore the algorithm produces a correct digitization of the monotone conic segment. ∎