Geometry Seminar

---

Incremental Planar Nearest Neighbor Queries with Optimal Query Time

Speaker: John Iacono, Université libre de Bruxelles

Location: Warren Weaver Hall 1314 and on Zoom

Date: Tuesday, January 27, 2026, 6 p.m.

Synopsis:

In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal \(O(\log n)\) time while supporting insertions in \(O(\log^{1+ε}n)\) time. No previous data structure was known that supports \(O(\log n)\)-time queries and polylog-time insertions. In order to achieve logarithmic queries our data structure uses a new technique related to fractional cascading that leverages the inherent geometry of this problem. Our method can be also used in other semi-dynamic scenarios.

Joint work with Yakov Nekrich.

Notes:

In person.  Plz contact Boris Aronov for if you are not NYU-affiliated and want to attend in person, and/or to be put on the mailing list and get the Zoom information.