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.
