TAOCP 7.1.3 Exercise 181

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 181. [HM20] [HM20] Explain how to subdivide a general conic (168) with rational coefficients into monotonic parts so that Algorithm T applies.

Verified: yes
Solve time: 2m34s

Let the conic be given by

$$ F(x,y)=ax^2+bxy+cy^2+dx+ey+f=0,\qquad a,b,c,d,e,f\in\mathbb{Q}. $$

Let $C$ denote its real locus.

We first isolate the finitely many points where the projection behavior can change. These are precisely the singular points and the points with vertical or horizontal tangents.

A point is singular when

$$ F(x,y)=F_x(x,y)=F_y(x,y)=0. $$

On a nondegenerate conic this system has no solution or a single point, and in any case it is finite.

A point has a vertical tangent exactly when $F_y(x,y)=0$ and $F(x,y)=0$. Similarly, it has a horizontal tangent exactly when $F_x(x,y)=0$ and $F(x,y)=0$. Since $F_x$ and $F_y$ are affine-linear, each of these systems consists of at most two points on the conic unless the conic degenerates into a line, in which case the conclusion below becomes even simpler.

Let $P\subset C$ be the finite set of all singular points together with all points satisfying $F_x=0$ or $F_y=0$. Consider the curve $C\setminus P$. Each connected component of $C\setminus P$ is a smooth open arc on which $F_x\neq 0$ and $F_y\neq 0$ throughout.

Fix such a component $A$. Since $A$ is a one-dimensional smooth curve, it admits a continuous parametrization $\gamma:(\alpha,\beta)\to A$, with $\gamma(t)=(x(t),y(t))$, where $x(t),y(t)$ are continuously differentiable and $(x'(t),y'(t))\neq (0,0)$.

We now show that on $A$, the projection onto the $x$-axis is injective, i.e. $x(t)$ is strictly monotone. Along the curve,

$$ F_x(x(t),y(t)),x'(t)+F_y(x(t),y(t)),y'(t)=0. $$

On $A$, we have $F_y\neq 0$ everywhere, so a vertical tangent (which would require $x'(t)=0$) cannot occur. Indeed, if $x'(t_0)=0$, then the tangent vector would be vertical, which forces $F_y(x(t_0),y(t_0))=0$, contradicting the definition of $A$. Hence $x'(t)\neq 0$ for all $t\in(\alpha,\beta)$.

Since $x'(t)$ is continuous and never zero on a connected interval, its sign is constant on $(\alpha,\beta)$. Therefore $x(t)$ is strictly monotone, hence injective. This proves that each connected component of $C\setminus P$ is $x$-monotone.

The same argument applies symmetrically to $y(t)$: on each component of $C\setminus P$, the condition $F_x\neq 0$ ensures $y'(t)\neq 0$ everywhere, hence $y(t)$ has constant sign of derivative and is strictly monotone. Thus each component is also $y$-monotone.

We now refine the decomposition in the way required by Algorithm T. The set $P$ partitions each connected component of $C$ into finitely many open arcs (since $P$ is finite and each removal of a point from a one-dimensional manifold splits it into at most two pieces). On each resulting arc, either $F_y\neq 0$ throughout or $F_x\neq 0$ throughout (indeed both hold, but we use either condition depending on projection).

Consequently, each arc is the image of an interval under a map that is injective in at least one coordinate projection: if we use $x$-projection, $x(t)$ is strictly monotone; if we use $y$-projection, $y(t)$ is strictly monotone. Hence each arc can be traversed unambiguously by stepping in the coordinate direction corresponding to the monotone projection, which is exactly the requirement needed for Algorithm T.

Finally, in degenerate cases the conic is a line, a pair of lines, or a point. A line has everywhere constant nonzero slope or is vertical, and is already globally monotone in either $x$ or $y$, so at most one cut at a coordinate-extreme point is needed. Intersections of two lines reduce to finitely many line segments, each trivially monotone. A single point requires no subdivision.

Thus, by subdividing the conic at all points where $F_x=0$, $F_y=0$, or $F_x=F_y=0$, we obtain finitely many arcs, each of which is monotone in a coordinate projection, so Algorithm T applies. ∎