Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game

Thomas Byrne, Sándor P. Fekete, Jӧrg Kalcsics, Linda Kleist

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain R of normalized dimensions of 1 and ρ≥1, and distances are measured according to the Manhattan metric. We show that the family of 'balanced' facility configurations (in which the Voronoi cells of individual facilities are equalized with respect to a number of geometric properties) is considerably richer in this metric than for Euclidean distances. Our main result considers the 'One-Round Voronoi Game' with Manhattan distances, in which first player White and then player Black each place n points in R; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if ρ≥n; for all other cases, we present a winning strategy for Black.
Original languageEnglish
Title of host publicationWALCOM: Algorithms and Computation
Subtitle of host publication15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 – March 2, 2021, Proceedings
EditorsRyuhei Uehara, Seok-Hee Hong, Subhas C. Nandy
Number of pages19
ISBN (Electronic)978-3-030-68211-8
Publication statusE-pub ahead of print - 16 Feb 2021

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game'. Together they form a unique fingerprint.

Cite this