Exact Geometric Computation

点击翻译按钮获取中文摘要

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. ***