HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Preprints >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/775
Title: Competitive facility location : the Voronoi game
Authors: Ahn, Hee-Kap
Cheng, Siu-Wing
Cheong, Otfried
Golin, Mordecai J.
Van Oostrum, Rene
Keywords: Voronoi game
Competitive facility location
Nearest-neighbor rule
Issue Date: 2001
Citation: To be published in Theoretical Computer Science
Abstract: 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 also consider a variation where players can play more than one point at a time for the circle arena.
URI: http://hdl.handle.net/1783.1/775
Appears in Collections:CSE Preprints

Files in This Item:

File Description SizeFormat
vorgame.pdf138KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.