2026-08-25T17:34:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27177 2026-08-25T13:18:16Z ddc:004 open_access

The Prophet and the Voronoi Diagram Har-Peled, Sariel Voronoi diagram prophet inequality secretary problem Consider a stream of n random points (say, from the unit square) arriving one by one, where a player must make an immediate and irreversible decision upon each point’s arrival, whether to pick it. The player must pick exactly one such 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 - Õ(1/√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 both the optimal payoff and this strategy’s payoff are larger by a factor of Θ(log n) than the average payoff. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sariel Har-Peled 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.41 urn:nbn:de:0030-drops-271779 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.41 eng https://creativecommons.org/licenses/by/4.0/legalcode