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.