\input header
\input epsf
\section{Tangent hulls}

If a curve is represented by a polygon and has the hodograph property, then it is clear that we can represent the first derivative by another polygon, and that this can itself be hulled to give information about the range of variation of the first derivative.  Such a hull is called a {\bf Tangent Hull}.

We can use this more explicit information through an additional API call which returns the tangent hull.  It can be applied in two ways: it may be possible to revise the notion of simplicity so that it applies much earlier, and it may be possible to be much more selective about the subproblems which are refined.  Here are two examples.

\subsection{In Plane-Curve Intersection}

If the dot product of the tangent and the plane normal is of a constant sign, the curve intersects the plane in at most one point.  We can test for this condition by looking at the extent of the tangent hull along the normal direction.   If subdivision is carried out until  all vectors within the tangent hull have the same sign dot product with the normal (and we can test this by just looking at the corners of the hull volume) it will have separated the intersection points into separate subproblems.  

Once this has been achieved, bracketting will provide a robust homing in on the exact positions of those intersection points, and may be faster.  This requires that the curve supports both the subdivision API and the parametric API, but most of the curves that we deal with do in fact support both\footnote{$^1$}{It can be argued that the binary subdivision structure implies a parametrisation. The parameter value is the binary fraction that the sequence of subdivisions implies.  This means that all subdivision curves are also parametric.  This idea is important for the analysis of the nature of subdivision curves, but it is not really a practical tool for providing evaluation of points on the curve from parameter values.}.
Whether such bracketting is actually any faster than continuing the subdivision depends on the curve and the amount of optimisations the two codes have.

\subsection{In Closest Approach}

If the curves are known to be $C1$, then any solution in the interior of the first curve must have $dP/du.[P-Q] = 0$.    We can make a hull of $[P-Q]$ from the individual hulls of $P$ and $Q$, and then check whether, for values inside the hulls of $T=dP/du$ and of $[P-Q]$, the dot product can change sign.

If it cannot, then there is no solution in that sub-problem, and it need not be subdivided.
This can be very effective at removing sub-problems which need not be considered.

\subsection{Derivative Hull variants}

Some speculative comments.

The simple thing to do is just to take the hull of the first derivative vectors using the hodograph property.  However, if we are considering geometric properties of the curve, the tangent vector magnitude (the 'speed') is not particularly relevant, but it does affect the shape and size of the derivative hull.

There is also the possibility of taking the raw derivative hull $H_t$, and finding a hull for the unit tangent vector.  A possible algorithm for this is to find the intersection of the cone, $C$, containing all positive linear combinations of positions in $H_t$ and the origin, with the surface of the unit sphere.  This intersection can in turn be hulled, giving a hull within which unit tangent vectors must lie.

Since most of the tests that we are likely to use the tangent hull for depend only on the directions, this does not give any advantage, but the surface analogue is more useful.

Higher derivatives can also be hulled, and the distinctions between the raw second derivative, the component of second derivative normal to the tangent, and the unit vectors along those components might well be relevant.  These hulls would only be applicable in interrogations dependent on second derivatives.

\end
