TAOCP 7.1.3 Exercise 184
Let Algorithm T be applied to the endpoints $(x,y)$ and $(x',y')$ with quadratic form $Q$, producing a sequence of edges determined by the sign changes of $Q$ along the digitized path from $(x,y)$ to...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 184. ▶ [M22] [M22] Find a quadratic form Q′(x, y) so that, when Algorithm T is applied to (x′, y′), (x, y), and Q′, it produces exactly the same edges as it does from (x, y), (x′, y′), and Q, but in the reverse order. Hint: There is a simple answer.
Verified: yes
Solve time: 1m07s
Solution
Let Algorithm T be applied to the endpoints $(x,y)$ and $(x',y')$ with quadratic form $Q$, producing a sequence of edges determined by the sign changes of $Q$ along the digitized path from $(x,y)$ to $(x',y')$.
The construction of Algorithm T is symmetric in the sense that its step selection depends only on the sign of the evaluated quadratic form at successive candidate lattice points. Reversing the order of generated edges therefore corresponds to reversing the direction of traversal of the same geometric locus, which in turn reverses all sign tests that control edge selection.
Consider replacing the quadratic form $Q$ by its negation
$$ Q'(x,y) = -Q(x,y), $$
while simultaneously exchanging the roles of the endpoints $(x,y)$ and $(x',y')$.
Under Algorithm T, every decision made at a lattice point is determined by whether $Q(\cdot)$ is positive or negative. Replacing $Q$ by $-Q$ reverses all such inequalities, so every step that would have advanced in one direction under $Q$ is taken in the opposite direction under $Q'$. Since the endpoints are also interchanged, the resulting traversal follows exactly the same sequence of edges as the original computation, but in reverse order.
Thus $Q'(x,y) = -Q(x,y)$ produces a digitization with identical edges, listed in reverse order when Algorithm T is applied to $(x',y')$, $(x,y)$, and $Q'$.
This completes the proof. ∎