RIA: Towards Robust Geometric Computations

几何计算和所有数值过程一样，极易产生舍入误差。然而，几乎没有数值分析的文献直接适用于几何计算和很少的几何文献直接解决这个问题。即使对于直线相交这种最基本的几何运算，也没有鲁棒高效的算法。使困难更加复杂的是，许多几何算法重复使用先前计算过的数据进行计算迭代。因此，大多数执行几何计算的应用程序都采用临时方法来克服数值困难。本研究针对几何计算中的一些主要问题和已提出的处理舍入误差的方法。它建立在这个领域的主要研究者以前所做的工作的基础上，并扩展了结果，使应用计算几何和计算机图形学的更复杂问题能够实现健壮的解决方案。

Geometric computations, like all numerical procedures, are extremely prone to roundoff error. However, virtually none of the numerical analysis literature directly applies to geometric calculations and little of the geometry literature directly addresses this problem. Even for line intersection, the most basic geometric operation, there is no robust and efficient algorithm. Compounding the difficulties, many geometric algorithms perform iterations of calculations reusing previously computed data. As a result, most of the applications performing geometric computations resort to ad-hoc methods to overcome the numerical difficulties. This research is directed towards some of the main issues in geometric computations and the methods that have been proposed to handle roundoff errors. It builds upon work done previously by the principal investigator in this area and expand the results to enable and implement robust solutions to more complex problems of applied computational geometry and computer graphics.