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.