Improved Bounds for Discrete Voronoi Games

Mark de Berg; Geert van Wordragen

doi:10.1007/978-3-031-38906-1_20

Improved Bounds for Discrete Voronoi Games

Mark de Berg^*, Geert van Wordragen

^*Tämän työn vastaava kirjoittaja

Tietotekniikan laitos

Eindhoven University of Technology

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

5 Lataukset (Pure)

Abstrakti

In the planar one-round discrete Voronoi game, two players P and Q compete over a set V of n voters represented by points in R². First, P places a set P of k points, then Q places a set Q of ℓ points, and then each voter v∈ V is won by the player who has placed a point closest to v. It is well known that if k= ℓ= 1, then P can always win n/3 voters and that this is worst-case optimal. We study the setting where k> 1 and ℓ= 1. We present lower bounds on the number of voters that P can always win, which improve the existing bounds for all k⩾ 4. As a by-product, we obtain improved bounds on small ε -nets for convex ranges for even numbers of points in general position.

Alkuperäiskieli	Englanti
Otsikko	Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
Toimittajat	Pat Morin, Subhash Suri
Kustantaja	Springer
Sivut	291-308
Sivumäärä	18
ISBN (painettu)	978-3-031-38905-4
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-031-38906-1_20
Tila	Julkaistu - 2023
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	International Symposium on Algorithms and Data Structures - Montreal, Kanada Kesto: 31 heinäk. 2023 → 2 elok. 2023 Konferenssinumero: 18

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Kustantaja	Springer
Vuosikerta	14079 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	International Symposium on Algorithms and Data Structures
Lyhennettä	WADS
Maa/Alue	Kanada
Kaupunki	Montreal
Ajanjakso	31/07/2023 → 02/08/2023

Pääsy asiakirjaan

10.1007/978-3-031-38906-1_20

Improved Bounds for Discrete Voronoi GamesAccepted author manuscript, 816 KB

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

Siteeraa tätä

de Berg, M., & van Wordragen, G. (2023). Improved Bounds for Discrete Voronoi Games. teoksessa P. Morin, & S. Suri (Toimittajat), Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings (Sivut 291-308). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 14079 LNCS). Springer. https://doi.org/10.1007/978-3-031-38906-1_20

de Berg, Mark ; van Wordragen, Geert. / Improved Bounds for Discrete Voronoi Games. Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Toimittaja / Pat Morin ; Subhash Suri. Springer, 2023. Sivut 291-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fe5008a63927446f899dd63e1602acd9,

title = "Improved Bounds for Discrete Voronoi Games",

abstract = "In the planar one-round discrete Voronoi game, two players P and Q compete over a set V of n voters represented by points in R2. First, P places a set P of k points, then Q places a set Q of ℓ points, and then each voter v∈ V is won by the player who has placed a point closest to v. It is well known that if k= ℓ= 1, then P can always win n/3 voters and that this is worst-case optimal. We study the setting where k> 1 and ℓ= 1. We present lower bounds on the number of voters that P can always win, which improve the existing bounds for all k⩾ 4. As a by-product, we obtain improved bounds on small ε -nets for convex ranges for even numbers of points in general position.",

keywords = "Competitive facility location, Spatial voting theory, Voronoi games",

author = "{de Berg}, Mark and {van Wordragen}, Geert",

note = "Funding Information: MdB is supported by the Dutch Research Council (NWO) through Gravitation grant NETWORKS-024.002.003. Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; International Symposium on Algorithms and Data Structures, WADS ; Conference date: 31-07-2023 Through 02-08-2023",

year = "2023",

doi = "10.1007/978-3-031-38906-1_20",

language = "English",

isbn = "978-3-031-38905-4",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "291--308",

editor = "Pat Morin and Subhash Suri",

booktitle = "Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings",

address = "Germany",

}

de Berg, M & van Wordragen, G 2023, Improved Bounds for Discrete Voronoi Games. julkaisussa P Morin & S Suri (toim), Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vuosikerta 14079 LNCS, Springer, Sivut 291-308, International Symposium on Algorithms and Data Structures, Montreal, Kanada, 31/07/2023. https://doi.org/10.1007/978-3-031-38906-1_20

Improved Bounds for Discrete Voronoi Games. / de Berg, Mark; van Wordragen, Geert.
Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. toim. / Pat Morin; Subhash Suri. Springer, 2023. s. 291-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 14079 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

T1 - Improved Bounds for Discrete Voronoi Games

AU - de Berg, Mark

AU - van Wordragen, Geert

N1 - Conference code: 18

PY - 2023

Y1 - 2023

N2 - In the planar one-round discrete Voronoi game, two players P and Q compete over a set V of n voters represented by points in R2. First, P places a set P of k points, then Q places a set Q of ℓ points, and then each voter v∈ V is won by the player who has placed a point closest to v. It is well known that if k= ℓ= 1, then P can always win n/3 voters and that this is worst-case optimal. We study the setting where k> 1 and ℓ= 1. We present lower bounds on the number of voters that P can always win, which improve the existing bounds for all k⩾ 4. As a by-product, we obtain improved bounds on small ε -nets for convex ranges for even numbers of points in general position.

AB - In the planar one-round discrete Voronoi game, two players P and Q compete over a set V of n voters represented by points in R2. First, P places a set P of k points, then Q places a set Q of ℓ points, and then each voter v∈ V is won by the player who has placed a point closest to v. It is well known that if k= ℓ= 1, then P can always win n/3 voters and that this is worst-case optimal. We study the setting where k> 1 and ℓ= 1. We present lower bounds on the number of voters that P can always win, which improve the existing bounds for all k⩾ 4. As a by-product, we obtain improved bounds on small ε -nets for convex ranges for even numbers of points in general position.

KW - Competitive facility location

KW - Spatial voting theory

KW - Voronoi games

UR - http://www.scopus.com/inward/record.url?scp=85172734846&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_20

DO - 10.1007/978-3-031-38906-1_20

M3 - Conference article in proceedings

AN - SCOPUS:85172734846

SN - 978-3-031-38905-4

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 308

BT - Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer

T2 - International Symposium on Algorithms and Data Structures

Y2 - 31 July 2023 through 2 August 2023

ER -

de Berg M, van Wordragen G. Improved Bounds for Discrete Voronoi Games. julkaisussa Morin P, Suri S, toimittajat, Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Springer. 2023. s. 291-308. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-38906-1_20