This research is to investigate fundamental algorithms for computer aided geometric design based on algebraic methods operating in a finite precision computing environment. This proposal is motivated by the basic intersection problems in computer aided geometric design: curve-curve intersection, curve-surface intersection, and surface-surface intersection. The investigators plan to explore efficient and robust methods for computing the points of intersection between two nonplanar rational curves, the points of intersection between a rational curve and a rational surface, and the curve of intersection between two rational surface patches. Several other basic and supporting problems will also be addressed. These problems include: finding a tight upper bound on the number of intersection points between two non-planar rational curves of known degrees, determining if a rational surface patch is improperly parametrized, deciding how base points affect the degree of a parametric patch in floating point arithmetic, and developing exact global and approximate local implicitization algorithms for rational surface patches. The research will also investigate numerically stable alternatives to Euclid's Greatest Common Division algorithm for floating point arithmetic. This will also involve a combination of theoretical, empirical, and practical work. The investigators plan first to develop the mathematical theory, then to test this theory on curves and surfaces used in industrial applications, and finally to code the algorithms into practical software.
