Competitive location problems : balanced facility location and the one-round Manhattan Voronoi game

Byrne, Thomas and Fekete, Sándor P. and Kalcsics, Jörg and Kleist, Linda; Uehara, Ryuhei and Hong, Seok-Hee and Nandy, Subhas C., eds. (2021) Competitive location problems : balanced facility location and the one-round Manhattan Voronoi game. In: WALCOM. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) . Springer, Virtual, Online, pp. 103-115. ISBN 9783030682118 (https://doi.org/10.1007/978-3-030-68211-8_9)

[thumbnail of Byrne-etal-WALCOM2021-Competitive-location-problems]
Preview
 Text. Filename: Byrne_etal_WALCOM2021_Competitive_location_problems.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (2MB)| Preview

Abstract

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 configurations (in which the Voronoi cells of individual facilities are equalized with respect to geometric properties) is 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.

ORCID iDs

Byrne, Thomas ORCID logoORCID: https://orcid.org/0000-0003-0548-4086, Fekete, Sándor P., Kalcsics, Jörg and Kleist, Linda; Uehara, Ryuhei, Hong, Seok-Hee and Nandy, Subhas C.
CORE (COnnecting REpositories)