Exact Geometric Computation

9402464 Yap几何算法出现在许多应用领域。这种算法的非鲁棒性是人们关注的主要问题。由于几何算法的特点是同时存在数值和组合元素，因此这里的非鲁棒性问题显得比纯数值计算更棘手。有证据表明，当前基于机器浮点运算的实现方法在处理非鲁棒性方面根本是不足的。本项目建议使用精确计算来实现这些算法。这是一种全新的计算范式，包含了一套丰富的计算策略。初步分析表明，精确计算对于一类重要的问题（理性有界深度问题）是非常有效的。研究的两个目标是建立这种方法的实际可行性。探讨精确计算的理论基础。实际目标涉及关键软件包的设计，并将其应用于重要的应用领域。这里的一个新主题是精度敏感算法领域，它有望激发新的算法研究，以解决使用传统复杂性参数似乎难以解决的问题。＊＊＊

9402464 Yap Geometric algorithms arise in many application areas. The non- robustness of such algorithms is of major concern. As geometric algorithms are characterized by the presence of both numerical and combinatorial elements, non-robustness problems here appear more intractable than in purely numerical computation. Evidence suggests that current implementation approaches, based on machine floating-point arithmetic, are fundamentally inadequate in dealing with non-robustness. This project proposes to use exact computation for implementing such algorithms. This is a fundamentally new computing paradigm that includes a rich set of computational tactics. Initial analysis indicates that exact computation can be quite effective for an important class of problems (the rational bounded-depth problems). The two goals of the research are To establish the practical viability of this approach. To investigate the theoretical bases for exact computation. The practical goal involves the design of key software packages, and to apply this to a significant application area. A new topic here is the area of precision-sensitive algorithms, which promises to stimulate new algorithmic research on problems which seems intractable using traditional complexity parameters. ***