The one-round Voronoi game

In the one-round Voronoi game, the first player chooses an n-point set IN in a square Q, and then the second player places another n-point set 8 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 U B. We give a (randomized) strategy for the second player that always guarantees him a payoff of at least (1) under bar2 + alpha, for a constant alpha > 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) under bar2.
Publisher
SPRINGER-VERLAG
Issue Date
2004-01
Language
ENG
Keywords

LOCATION; MODELS

Citation

DISCRETE COMPUTATIONAL GEOMETRY, v.31, no.1, pp.125 - 138

ISSN
0179-5376
DOI
10.1007/s00454-003-2951-4
URI
http://hdl.handle.net/10203/304
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
2002-034.pdf(203.32 kB)Download
  • Hit : 443
  • Download : 251
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 18 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0