The One-Round Voronoi Game

Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jiří Matoušek

Research output: Contribution to journalArticlepeer-review

Abstract

In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the fraction of the area of Q occupied by the regions of the points of B in the Voronoi diagram of W ∪ B. We give a (randomized) strategy for the second player that always guarantees him a payoff of at least 1/2 + α, for a constant α > 0 and every large enough n. This contrasts with the one-dimensional situation, with Q = [0, 1], where the first player can always win more than 1/2.

Original languageEnglish (US)
Pages (from-to)125-138
Number of pages14
JournalDiscrete and Computational Geometry
Volume31
Issue number1
DOIs
StatePublished - Jan 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'The One-Round Voronoi Game'. Together they form a unique fingerprint.

Cite this