Geometry Seminar

---

The Road to the Closest Point is Paved by Good Neighbors

Speaker: Ben Raichel, UT Dallas

Location: Online

Date: Tuesday, October 28, 2025, 2 p.m.

Synopsis:

Given a set P of n points in ℝ^d, and a parameter ε∈(0,1), we present a new construction of a directed graph G, of size O(n/ε^d), such that (1+ε)-ANN queries can be answered by performing a greedy walk on G, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is O(ε^−dlogΨ), where Ψ is the spread of P. The new construction is surprisingly simple and should be practical.

Joint work with Sariel Har-Peled and Eliot W. Robson.

Notes:

On Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.