Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game

Thomas Byrne (), Sándor P. Fekete (), Jörg Kalcsics () and Linda Kleist ()
Additional contact information
Thomas Byrne: University of Strathclyde
Sándor P. Fekete: TU Braunschweig
Jörg Kalcsics: University of Edinburgh
Linda Kleist: TU Braunschweig

Annals of Operations Research, 2023, vol. 321, issue 1, No 4, 79-101

Abstract: 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 $$\rho \ge 1$$ ρ ≥ 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 $$\rho \ge n$$ ρ ≥ n ; for all other cases, we present a winning strategy for Black.

Keywords: Facility location; Competitive location; Manhattan distances; Voronoi game; Geometric optimization (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04976-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:321:y:2023:i:1:d:10.1007_s10479-022-04976-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04976-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().