\input CgHdr.tex
\begfile{CgN7.tex of March 7, 1983 5:27 PM --- Stolfi}
\notesformat
\inputtty % Your chance to enter \def\printfilestamp{F}

\chapcont{10}{Convex tracings}
\setcount0 28

\section {10.4. Common tangents}

[ ] tangents from a point to a polygon; linear algorithm
discuss bimodality of intercept on separator

[ ] distance between antipodal (= opposite?) tangents

[ ] maximally apart antipodal tangents
a. touch the polygon exactly once each
b. line joining points of contact is perpendicular to the tangents
c. length of that segment equals the diameter of the set

[ ] same true for minimally apart antipodal tangents

[ ] two disjoint convex polygons P and Q; consider antipodal tangents, one to P and one to Q

[ ] if (p,q) is the distance from P to Q, then the tangents at p and q are antipodal and are perpendicular to P and Q

[ ] a. disjoint convex sets have a separating line
b. even one parallel to a side of one of them (Hobby argument)

[ ] Take two disjoint convex polygons and wlog rotate the plane so that their separating line is vertical

[ ] Use car language; discuss states at leftmost and rightmost points

[ ] existence of exactly two outer common tangents by intecept on separator argument
existence of exactly two inner common tangents

[ ] computing the outer common tangents; **give clean linear algorithm and proof

[ ] give $log↑2$ algorithm based on separator intercept
give log algorithm based on predicates
RA: A is to the right of b
RB: B is to the right of a
and cutting up the product space
discuss L-shape binary search in detail with invariants maintained

[ ] new observation that eliminates L-search

[ ] remark on always following rightmost car; prove that when we switch from one tracing to the next, the car moves forwards. Thus result is a convex tracing, the convex hull.

[ ] discuss leftmost car; concept of monostrofic (??) tracing. Remark that common tangent computation algorithms apply also to monostrofic tracings.

[ ] derive Jarvis’s algorithm for CH from same ideas on n cars spinning on n points.

[ ] delop carefully log search algorithm for bimodal function zero crossings, or maxima and minima
apply to get log algorithm for tangents

\par\vfill\eject\end