Approximate Algebraic Methods in Computer Aided Geometric Design

本研究旨在探讨在有限精度计算环境下，基于代数方法的计算机辅助几何设计的基本算法。基于计算机辅助几何设计中的基本相交问题：曲线-曲线相交、曲线-曲面相交、曲面-曲面相交。研究人员计划探索有效且稳健的方法来计算两条非平面有理曲线之间的交点、有理曲线与有理曲面之间的交点以及两个有理曲面斑块之间的交点。还将讨论其他几个基本和支持性问题。这些问题包括：寻找已知度数的非平面有理曲线交点个数的紧上界，确定有理曲面贴片参数化是否不正确，确定浮点算法中基点对参数贴片程度的影响，并对有理曲面贴片开发精确的全局和近似局部隐式算法。该研究还将研究欧几里得最大公除法算法在浮点运算中的数值稳定替代方案。这也将涉及理论、实证和实际工作的结合。研究人员计划首先发展数学理论，然后在工业应用中使用的曲线和曲面上测试这一理论，最后将算法编码到实用软件中。

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.