Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/775

Competitive facility location: the Voronoi game

Authors Ahn, HK
Cheng, SW
Cheong, O
Golin, M
van Oostrum, R
Issue Date 2004
Source Theoretical computer science , v. 310, (1-3), 2004, JAN 1, p. 457-467
Summary We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We permit variations where players can play more than one point at a time, and show that the first player can ensure that the second player wins by an arbitrarily small margin. (C) 2003 Elsevier B.V. All rights reserved.
Subjects
ISSN 0304-3975
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
vorgame.pdf 142065 B Adobe PDF