The Voronoi War: AI Beats the Prophet

Sariel Har-Peled

Latest version: v1, posted 2026-10-10. PDF · Read online

The PDF is authoritative. The Markdown copy, when available, is provided for browser reading.

Version history

Personal comments

This research was triggers by my wish to try out the AI tools. I remembered the open problem in the end of my recent paper, and I was wondering if I could solve it using AI. The problem was interesting to me, but not quite interesting enough for me to work on it actively. So I asked the AI. It pretty quickly answered the question and provided an (essentially tight) answer. I then opened the Pandora box asking for various models and behaviors.

As a quick summary, the previous paper defined a geometric secretary-problem type game, where the points are chosen randomly and uniformly in the unit square, and the payoff is the area of the cell selected by the user. The previous paper showed a \(O(1)\) approximation. The first natural question was what happens if instead of random points, you get a random permutation of the points (you still don't know the points in advance).

The AI showed that the permutation version has \(O( \log n)\) competitive strategy (i.e., not having uniform sampling hurt you), and this is tight.

There are several nice results in this writeup. The neatest one might be the following game: You have cycle with \(n\) vertices on it, and you are given the vertices one by one in random order, You have to guess what is the last vertex. Whenever a vertex \(i\) is exposed, you can chose either of its empty neighbors as the future location of the final vertex in the permutation. You can not choose the vertex \(i\) itself. Surprisingly, this game has a tight \(O(\sqrt(n))\) competitive strategy.

Ultimately, the AI was even able to get \((1+\epsilon)\)-approximation to the largest cell by slightly modifying the sampling model. This result in retrospect is not surprising - it was really about asking the right question - the tools were really there in the original paper.

So how was the experience?

It was quite interesting! There is a bit of a disappointment in feeling the lost opportunity for not bothering to sit down and figuring out the results on my own, but clearly I was not going to do it on my own -- too much work for too little return. I might have worked on it if I knew there were so many nice results within reach.

What would I do with the paper?

I don't know. Well, the results are definitely of publishable quality in the old-world (i.e., 3 months ago). I consider the original paper still a better contribution than this paper, because it defined the model and problem, but this paper clearly have move intellectual heft. I wish we were in a universe where I could just post it to the arxiv and forget about it (I might still just do it). The paper does not have any important results - it was an tour of exploration of a problem I was interested in, and I learned quite a bit (the AI figuring things out triggered by my questions).

Is it readable?

Absolutely. I spent quite a bit of time with the AI ensuring the writeup is readable, and in addition I read and edited parts of the writeup. I stand behind the results. If I believed the result was publishable in the new world order, I might have spent more time polishing the writeup. But for now, I am putting it out in its current condition.

The figures

The figures are quite decent and were generated by the AI. The AI used my Julia library (initially written by me, now largely by AI) to write short programs to draw the figures into ipe/pdf files. I was positively surprised by the quality of the results.

AI tools used

Most of the research was done using Astra on high, extra high, or max. Writing benefited from doing passes for simplification with Claude (Fable). Most of the research was done using the web interface, the later steps using codex and claude cli tools. The research was facilitated by OpenAI providing me with free researcher access, and similarly Anthropic providing a much cheaper researcher access to their models (the OpenAI access provided supposedly cost $200 a month, and the Anthropic one is $100 a month - they both seems quite more valuable than these prices suggest).

What about the future?

I don't know. The current publishing model seems completely broken at least in the near future. Should I really be considered an author of this paper? I might have spent 1-2 days on this project. It feels like cheating (but frankly I had the same feeling when I wrote my first few papers - it always felt somehow too easy [there it was months, now it is hours]).

My hope is that in the end of the day, the blind greedy run after trophies would calm down. Because all the easy trophies had been collected by OpenAI or Anthropic, and what would remain would be AI hard. As a research community we would have to shift from answering questions to asking the right questions. Not necessarily a bad trade in the long run.