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.