Geometry Seminar

---

Delaunay Triangulations with Predictions

Speaker: Sergio Cabello, University of Ljubljana

Location: Online

Date: Tuesday, April 21, 2026, 2 p.m.

Synopsis:

I will talk about algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set \(P\) of \(n\) points in the plane and a triangulation \(G\) that serves as a "prediction" of the Delaunay triangulation, we would like to use \(G\) to compute the correct Delaunay triangulation \(\mathrm{DT}(P)\) more quickly when \(G\) is "close" to \(\mathrm{DT}(P)\). We will see a variety of results under different deterministic and probabilistic settings.

Joint work with Timothy M. Chan and Panos Giannopoulos, available at https://arxiv.org/abs/2601.08106.

Notes:

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