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

这个项目研究贪婪的三角剖分和相关的邻近问题，特别关注高效算法的开发。正在研究的课题包括：二维和三维贪婪三角剖分的新算法；测试高维三角剖分中的边兼容性的数据结构；高维贪婪三角剖分的数据结构；高维的近邻枚举算法；以及逼近最小重量三角剖分的新的交替三角剖分方法。最坏情况和算法都在研究中。主要关注的是欧几里德空间中的顺序算法，但并行算法和其他距离度量也可能被研究。本科生参与了这个项目。

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.