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.