Complete Subdivision Algorithm for Intersecting Bezier Curves

and surfaces is a major issue in geometric modeling.
Recently, efficient and fully robust algorithms have
been constructed for low degree algebraic objects.
These algorithms are based on exact algebraic algorithms.

In this talk, we consider the numerically-based
algorithms favored by practitioners in geometric
modeling. These are fast but nonrobust.
In particular, we consider the subdivision approach
for intersecting Bezier curves. Unfortunately,
current algorithms are incomplete:
they use an arbitrary $\epsilon$ cut-off
to stop the subdivision process. At the
cut-off point, a presumed intersection may represent
no intersection or multiple intersections.
In this talk, we give a complete subdivision algorithm
for intersecting a pair of Bezier curves.

We first describe our algorithm for "elementary curves",
i.e., graphs of convex or concave functions.
This is then extended to general Bezier curves.
A key contribution is the introduction of
"geometric separation bounds" into subdivision algorithms.