Theory Seminar Series: Dr. Sariel Har-Peled, "The Prophet and the Voronoi Diagram."

Abstract: Consider a stream of n random points (say, from the unit square) arriving one by one, where a player has to make an irreversible immediate decision for each arriving point whether to pick it. The player has to pick a single point, and the payoff is the area of the cell of the picked point, in the final Voronoi diagram of all the points. We show that there is a simple strategy so that with probability >= 1 - O(1/sqrt(n)), the player's payoff is only a constant factor smaller than the optimal choice (i.e., the one made by the prophet). This competitiveness is somewhat surprising, as this payoff is larger by a factor of Theta( log n) than the average payoff.

Anti-prophet AI tools proved the following extensions (which we would discuss shortly). For arbitrary fixed sites in random order, an O(log n) approximation with constant probability and an almost matching Omega( log n/ log log n) expected competitive-ratio lower bound is shown, even with sqrt(n) selections (!). For families of known smooth i.i.d. densities, every approximation factor below 2 has vanishing success probability, even with polylogarithmically many selections---the expected best selected area is at most (1/2+o(1)) of the expected optimum.

Paper is on the arxiv: https://arxiv.org/abs/2604.23021
It appeared in ESA 2026 simplicity track.