RIA: Towards Robust Geometric Computations

几何计算，像所有的数值计算一样， 容易犯圆缺错误。 然而，几乎没有一个数字 分析文献直接适用于几何计算， 很少有几何学文献直接论述这个问题。 即使对于最基本的几何运算--直线求交， 是没有鲁棒和有效的算法。 使困难更加复杂的是， 许多几何算法重复使用 以前计算的数据。 因此，大多数应用程序 执行几何计算求助于ad-hoc方法来克服 数字上的困难。 这项研究是针对一些 几何计算中的主要问题和方法 被建议处理圆形错误。 它建立在所做的工作之上 以前由首席研究员在这一领域，并扩大 结果，以实现和实施强大的解决方案， 应用计算几何和计算机图形学问题。

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.