Geometry Seminar

---

Revisiting Random Points: Combinatorial Complexity and Algorithms

Speaker: Elfarouk Harb, University of Illinois Urbana-Champaign

Location: Online Zoom-only

Videoconference link: https://youtu.be/THOV3vpuB-M

Date: Tuesday, September 24, 2024, 2 p.m.

Synopsis:

We consider a set \(P\) of \(n\) points chosen uniformly and independently from \([0, 1]^d \), where \(d\) is a constant. Such point sets are extremely well behaved and have been the subject of extensive study, leading to numerous known algorithmic, combinatorial, and concentration results on \(P\), and its structures (e.g. Delaunay Triangulation, Voronoi Diagrams, etc) under the umbrella of integral geometry. 

In this talk, we present some new results on the properties of\(P\), along with simpler proofs for several well-known results. The proofs are all combinatorial. We introduce linear-time algorithms for constructing the Delaunay triangulation, Euclidean minimum spanning tree (MST), and convex hull of \(P\), as well as new concentration bounds for the \(k\)-th pairwise distance. The MST algorithm is an interesting divide-and-conquer algorithm which might be of independent interest.

The talk assumes only mathematical maturity, and some geometric intuition. 

This is joint work with Sariel Har-Peled.

Notes:

Contact Boris Aronov to be placed on the mailing list with notifications and Zoom seminar info.