The perfidious polynomial: the numerical root-finding problem
in computer-aided geometric design algorithms
The problem of computing the real roots of polynomials on finite
intervals is fundamental to many basic algorithms in computer-aided
geometric design (intersections, distance measurements, etc.). In
floating-point arithmetic, the representation (choice of basis) for
polynomials may exert a significant influence on the accuracy with
which roots can be computed. Starting with the notorious Wilkinson
polynomial, we describe the superior stability properties of the
Bernstein polynomial form (the basis for the Bezier representation
of curves and surfaces). A partial ordering of polynomial bases
that are non-negative over a finite interval is induced by basis
transformations described by non-negative matrices. The Bernstein
basis is a "minimal element" under this partial ordering, and is
thus "optimally stable". No other commonly-used basis is known to
have this property.
------------------------------------------------------------------
Linear perturbation methods for ensuring topological consistency
of approximate geometrical representations
Many geometrical computations that are critical to computer-aided
design (e.g., surface intersections) do not admit exact closed-form
solutions, and the property of "topological consistency" is often
more important than nominal accuracy in approximate solutions. In
the context of the problem of intersecting Bezier surface patches,
we show how topological consistency can be enforced a posteriori on
approximate intersection curves. The approach entails determining
appropriate perturbations of the surface control points through the
solution of a linear system of equations. The overall strategy has
two main stages: a topology resolution and domain decomposition
scheme that dissects the intersection curve into "simple" pieces,
and application of the linear perturbation scheme to each of these
pieces.
------------------------------------------------------------------
MINKOWSKI GEOMETRIC ALGEBRA OF COMPLEX SETS
Algebraic operations on sets of complex numbers produce remarkably
rich geometrical structures, with diverse applications and connections
to science and engineering. For "simple" operands, such as circular
disks, precise descriptions of their algebraic combinations are
available in terms of the Cartesian and Cassini ovals, and
higher-order generalizations. Algorithms can be formulated to
approximate algebraic operations on complex sets with general
(piecewise-smooth) boundaries to a given precision. This "Minkowski
algebra of complex sets" is the natural generalization of (real)
interval arithmetic to sets of complex numbers. It provides a
versatile two-dimensional "shape operator" language, with connections
to mathematical morphology, geometrical optics, and stability analysis
of dynamic systems.