RUI: Proximity Problems with Applications to Greedy and Minimum Weight Triangulations

RUI：贪婪和最小权重三角剖分应用的邻近问题

• 批准号: 9301714
• 负责人: Matthew Dickerson
• 金额: $ 7.4万
• 依托单位: Middlebury College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-07-15 至 1997-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9301714&HistoricalAwards=false
• 关键词: RUI; Proximity; Problems; Applications; Greedy

This project investigates greedy triangulations and related proximity problems with a specific concern for the development of efficient algorithms. Topics under study include: new algorithms for the greedy triangulation in two and three dimensions; data structures for testing edge-compatibility in higher dimensional triangulations; of higher dimensional greedy triangulations; algorithms for near-neighbor enumeration in higher dimensions; and new alternate triangulation methods for approximating the minimum-weight triangulation. Both worst-case and algorithms are being explored. The primary concern is with sequential algorithms in Euclidean space, but parallel algorithms and other distance metrics may also be investigated. Undergraduate students are involved in the project.

这个项目研究贪婪三角剖分和相关的邻近问题，特别关注有效算法的发展。 正在研究的课题包括：新算法的贪婪三角形在二维和三维;数据结构的测试 高维三角剖分中的边相容性 更高维度的贪婪三角剖分;算法近邻枚举在更高的维度;和新的替代三角剖分方法近似 最小权三角测量 最差情况和 正在探索算法。 主要关注的是欧几里德空间中的顺序算法，但也可以研究并行算法和其他距离度量。 本科生参与了该项目。