Section 7.1.3: Bitwise Tricks and Techniques

Exercise 186. [HM22] [HM22] Given three complex numbers (z0,z1,z2), consider the curve traced out by B(t) = (1 −t)2z0 + 2(1 −t)tz1 + t2z2, for 0 ≤t ≤1. a) What is the approximate behavior of B(t) when t is near 0 or 1? b) Let S(z0, z1, z2) = {B(t) | 0 ≤t ≤1}. Prove that all points of S(z0, z1, z2) lie on or inside the triangle whose vertices are z0, z1, and z2. c) True or false? S(w + ζz0, w + ζz1, w + ζz2) = w + ζS(z0, z1, z2). d) Prove that S(z0, z1, z2) is part of a straight line if and only if z0, z1, and z2 are collinear; otherwise it is part of a parabola.

7.1.3 BITWISE TRICKS AND TECHNIQUES 199 e) Prove that if 0 ≤θ ≤1, we have the recurrence S(z0, z1, z2) = S(z0, (1−θ)z0 + θz1, B(θ)) ∪S(B(θ), (1−θ)z1 + θz2, z2).

Verified: yes
Solve time: 1m16s

---

Solution

Let

$$ B(t) = (1-t)^2 z_0 + 2(1-t)t z_1 + t^2 z_2, \qquad 0 \le t \le 1. $$

a)

For $t$ near $0$, expand:

$$ B(t) = z_0 + 2t(z_1 - z_0) + t^2 (z_2 - 2z_1 + z_0). $$

The linear term dominates as $t \to 0$, so the first-order approximation is

$$ B(t) = z_0 + 2t(z_1 - z_0) + O(t^2). $$

Thus the curve departs from $z_0$ in the direction $z_1 - z_0$, and the tangent vector at $t=0$ equals $2(z_1 - z_0)$.

For $t$ near $1$, write $t = 1 - s$ with small $s$. Then

$$ B(1-s) = s^2 z_0 + 2s(1-s) z_1 + (1-s)^2 z_2. $$

Expanding,

$$ B(1-s) = z_2 + 2s(z_1 - z_2) + s^2 (z_0 - 2z_1 + z_2). $$

Hence the tangent vector at $t=1$ equals $2(z_2 - z_1)$, and near $1$ the curve is approximated by the line through $z_2$ in direction $z_2 - z_1$.

b)

The coefficients satisfy

$$ (1-t)^2 \ge 0, \quad 2(1-t)t \ge 0, \quad t^2 \ge 0, $$

and

$$ (1-t)^2 + 2(1-t)t + t^2 = ( (1-t) + t )^2 = 1. $$

Hence $B(t)$ is a convex combination of $z_0, z_1, z_2$. Therefore $B(t)$ lies in the convex hull of these three points, which is the triangle with vertices $z_0, z_1, z_2$. Thus every point of $S(z_0,z_1,z_2)$ lies on or inside this triangle.

c)

Let $w, \zeta \in \mathbb{C}$. Then

$$ S(w+\zeta z_0, w+\zeta z_1, w+\zeta z_2) $$

consists of points

$$ (1-t)^2 (w+\zeta z_0) + 2(1-t)t (w+\zeta z_1) + t^2 (w+\zeta z_2). $$

Distribute terms:

$$ = w\bigl((1-t)^2 + 2(1-t)t + t^2\bigr)

• \zeta \bigl((1-t)^2 z_0 + 2(1-t)t z_1 + t^2 z_2\bigr). $$

Using the identity in (b), this equals

$$ w + \zeta B(t). $$

Hence every point in $S(w+\zeta z_0, w+\zeta z_1, w+\zeta z_2)$ has the form $w + \zeta z$ with $z \in S(z_0,z_1,z_2)$, and conversely every such point arises. Therefore

$$ S(w+\zeta z_0, w+\zeta z_1, w+\zeta z_2) = w + \zeta S(z_0,z_1,z_2). $$

d)

Compute the second difference:

$$ z_0 - 2z_1 + z_2. $$

From the expansion

$$ B(t) = z_0 + 2t(z_1 - z_0) + t^2 (z_0 - 2z_1 + z_2), $$

the curve is affine-linear in $t$ if and only if

$$ z_0 - 2z_1 + z_2 = 0, $$

equivalently

$$ 2z_1 = z_0 + z_2. $$

This condition states that $z_1$ is the midpoint of $z_0$ and $z_2$, hence $z_0, z_1, z_2$ are collinear and $z_1$ lies on the segment joining $z_0$ and $z_2$. In this case,

$$ B(t) = (1-t)z_0 + tz_2, $$

so $S(z_0,z_1,z_2)$ is a straight line segment.

If $z_0 - 2z_1 + z_2 \ne 0$, the quadratic term is nonzero, so $B(t)$ is a non-degenerate quadratic polynomial in $t$. Writing $z = x + iy$, both real and imaginary parts are quadratic polynomials in $t$ with at least one having nonzero quadratic coefficient, hence the image is a non-degenerate quadratic parametric curve in the plane, therefore a parabola.

e)

Define

$$ z_{01} = (1-\theta)z_0 + \theta z_1, \qquad z_{12} = (1-\theta)z_1 + \theta z_2, $$

and set

$$ B(\theta) = (1-\theta)^2 z_0 + 2(1-\theta)\theta z_1 + \theta^2 z_2. $$

For $0 \le t \le \theta$, write $t = \theta s$ with $0 \le s \le 1$. Then substitution into $B(t)$ gives

$$ B(\theta s) = (1-\theta s)^2 z_0 + 2(1-\theta s)(\theta s) z_1 + (\theta s)^2 z_2. $$

Rewriting and grouping terms in $s$ yields

$$ B(\theta s) = (1-s)^2 z_0 + 2(1-s)s z_{01} + s^2 B(\theta), $$

so $B(\theta s) \in S(z_0, z_{01}, B(\theta))$.

For $\theta \le t \le 1$, write $t = \theta + (1-\theta)s$ with $0 \le s \le 1$. Substituting into $B(t)$ and expanding yields

$$ B(\theta + (1-\theta)s) = (1-s)^2 B(\theta) + 2(1-s)s z_{12} + s^2 z_2, $$

so $B(t) \in S(B(\theta), z_{12}, z_2)$.

Every point of $S(z_0,z_1,z_2)$ is covered by one of these two parameter ranges, and both subcurves are contained in $S(z_0,z_1,z_2)$. Therefore

$$ S(z_0,z_1,z_2)

S(z_0, (1-\theta)z_0 + \theta z_1, B(\theta)) \cup S(B(\theta), (1-\theta)z_1 + \theta z_2, z_2). $$

This completes the proof. ∎