On the numerical condition of algebraic curves and surfaces 1. Implicit equations

Abstract

The numerical stability of algebraic curves and surfaces represented by implicit equations is investigated. The condition number at a point of a curve or surface is defined as the ratio of the maximum normal displacement of that point to the relative magnitude ε{lunate} of the random perturbations in the curve or surface coefficients, in the limit ε{lunate} → 0. Closed-form expressions for such condition numbers are presented, and the singular points of implicitly defined curves and surfaces are shown to be inherently ill-conditioned. Condition numbers for curve and surface intersections may be expressed in terms of those of the participant entities at the given point and certain geometric factors determined by the normal directions there. Tangential intersections are also seen to be inherently ill-conditioned. The dependence of condition numbers on the chosen multivariate polynomial basis is then examined. In particular, we compare power expansions about a given center, barycentric Bernstein bases over simplicial domains, and tensor-product Bernstein bases over rectangular domains. Configurations are enumerated in which one of these bases provides better conditioning than another at each point of every curve or surface in a given domain. The subdivision and degree elevation of multivariate Bernstein forms (barycentric or tensor-product) exhibit such behavior. © 1988.