The Design and Implementation of Geometric Algorithms

几何算法的设计与实现

• 批准号: 9002352
• 负责人: Bernard Chazelle
• 金额: $ 66.2万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-07-15 至 1993-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9002352&HistoricalAwards=false
• 关键词: Design; Implementation; Geometric; Algorithms

Research in three broad areas of computational geometry will be conducted. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. They include design and analysis of algorithms, concentrating mostly on problems involving nonlinear surfaces in dimensions higher than two, in particular, hidden surface removal, triangulations of real-algebraic varieties, and multidimensional searching, building an environment for implementing geometric algorithms and tools which can ultimately be used by researchers to produce and share geometric software, and design of robust geometric algorithms which entails tackling problems arising from finite precision arithmetic as well as the degeneracy of common real world geometric data.

在计算几何的三个广泛领域的研究将是 进行。 这些领域涵盖了从实际应用到 实现和调试几何图形时出现的注意事项 算法设计中出现的理论问题， 下界证明 它们包括算法的设计和分析， 主要集中在涉及非线性表面的问题， 大于2的尺寸，特别是隐藏表面的去除， 实代数簇的三角剖分和多维 搜索，建立一个环境， 研究人员最终可以使用的算法和工具， 生产和共享几何软件，并设计强大的几何 算法，这需要解决的问题所产生的有限 精确算法以及普通真实的世界的退化 几何数据