Exact Geometric Computation

精确的几何计算

• 批准号: 9402464
• 负责人: Chee Yap
• 金额: $ 7.3万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-01 至 1996-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9402464&HistoricalAwards=false
• 关键词: 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. ***

9402464 YAP几何算法在许多应用领域都出现。 这种算法的不健壮性是主要关注的。 由于几何算法的特征是存在数值和组合元素，因此，非舒适性问题似乎比纯粹的数值计算更棘手。 有证据表明，基于机器浮点算术的当前实施方法从根本上不足以应对非舒适性。 该项目建议使用精确的计算来实现此类算法。 这是一种从根本上进行新的计算范式，其中包括一系列计算策略。 初始分析表明，精确的计算对于重要类别的问题（理性有限的深度问题）可能非常有效。 研究的两个目标是建立这种方法的实际生存能力。 研究理论基础以进行精确计算。 实际目标涉及关键软件包的设计，并将其应用于重要的应用程序区域。 这里的一个新主题是精确敏感算法的领域，该算法有望刺激有关使用传统复杂性参数似乎很棘手的问题的新算法研究。 ***