# [metapost] Re: [metafont] Honza's puzzler

Larry Siebenmann laurent at math.toronto.edu
Sat Jan 22 05:43:31 CET 2005

```

*** A first tangent line census ***

Suppose b is a (composite) bezier path of length l >= 1
in Knuth's sense (ie the concatenation of l simple b'ezier
cubic arcs with 4 control points each).

PROBLEM. Find *all* the lines L passing through
a given point z and tangent to b.

Call this the tangent line census problem.

*Interior* tangent lines L, are the ones of most
interest, *interior* meaning that the intersection of L with
b does not include b(0) or b(l).

Here I use the discussion of yesterday to deal
completely with the case when  b  has NO CUSPS and
NO INFLEXIONS, and further turns through < 180 DEGREES.

Path  b  is then embedded and the foreward tangent ray at
b(0) and the backward tangent ray at b(l) intersect at a
point o (letter oh):

\ forward tangent ray at b(0)
\
\
\
\
\
\
<------------ o -------------------
backward ray   \               x x    b(l)
at  b(l)     \          x
\      x
\
\   x    path b
\
\  x
\
\ x

b(0)

These rays can be considered to be coordinate axes for R^2.

I now now distinguish 5 cases.

(a) z is in the closed quadrant opposite the one containing
b.  No interior tangent lines!

(b) z is in either of the two open quadrants adjacant to the
one containing  b. Exactly one interior tangent line
as explained yesterday!

(c) z  is on  b  but not on the axes.   There is exactly one
interior tangent line on  z  if z is not a corner of  b.
The is a whole sheaf of tangent lines through  z  if
if z is a corner of b.

Let Q be the interior of the quadrant containing b.

(d) z is in the unbounded component of Q - b, the one on the
concave side of  b. No interior tangent line through  z.

(e) z is in the bounded component of Q - b, the one near  o.
Exactly two interior tangent lines.

Proof of (e) Extend the linear segment o--z to meet  b  at a
point v and take the two tangent rays to  b at v.  Then
apply the CONCLUSION of yesterday twice to assure exactly
two interior tangent lines through z.

Summary: the number of interior tangent lines through z
depends on the position of z  as indicated
in brackets on this figure:

\ forward tangent ray at b(0)
\
\
\        [ 1 ]
[ 0 ]      \
\
\
<------------ o -------------------
backward ray   \               x x    b(l)
from b(l)    \  [ 2 ]   x
\      x
\
\   x    path b
[ 1 ]          \
\  x             [ 0 ]
\
\ x

b(0)

except for two unmarked cases
-- when z is on the axes: answer [ 0 ]
-- when z is on b : answer in (c).

The above easy but limited census can be used to attack
the general tangent line census problem by cutting up
general b into pieces of the above special sort.  The one
ticklish problem remaining will be to break up general b at
its inflexion points into pieces without inflexions.

Cheers

Laurent S.

PS.  Yesterday I wrote that the convergence ratio d'/d is
asymtotically d/D in the algorithm of Dirk and Jacko.  Dirk
says d/2D which is even better convergence, and he is
right. Sorry for the slip. I add that our calculations
assume that, at the point v of tangency, the curvature
radius R ot b at v exists and is finite.

```