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 book

1 Citation (Scopus)
11 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation: 15th International Conference and Workshops, WALCOM 2021, Proceedings
EditorsRyuhei Uehara, Seok-Hee Hong, Subhas C. Nandy
Place of PublicationCham, Switzerland
PublisherSpringer
Pages103-115
Number of pages13
ISBN (Electronic)9783030682118
ISBN (Print)9783030682101
DOIs
Publication statusPublished - 16 Feb 2021
Event15th International Conference on Algorithms and Computation, WALCOM 2021 - Virtual, Online
Duration: 28 Feb 20212 Mar 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12635 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Algorithms and Computation, WALCOM 2021
CityVirtual, Online
Period28/02/212/03/21

Keywords

  • competitive location
  • facility location
  • geometric optimization
  • Manhattan distances
  • Voronoi game

Fingerprint

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