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

^*Corresponding author for this work

Department of Computer Science

Eindhoven University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

4 Downloads (Pure)

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 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.

Original language	English
Title of host publication	Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
Editors	Pat Morin, Subhash Suri
Publisher	Springer
Pages	291-308
Number of pages	18
ISBN (Print)	978-3-031-38905-4
DOIs	https://doi.org/10.1007/978-3-031-38906-1_20
Publication status	Published - 2023
MoE publication type	A4 Conference publication
Event	International Symposium on Algorithms and Data Structures - Montreal, Canada Duration: 31 Jul 2023 → 2 Aug 2023 Conference number: 18

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	14079 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Symposium on Algorithms and Data Structures
Abbreviated title	WADS
Country/Territory	Canada
City	Montreal
Period	31/07/2023 → 02/08/2023

Keywords

Competitive facility location
Spatial voting theory
Voronoi games

Access to Document

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

Improved Bounds for Discrete Voronoi GamesAccepted author manuscript, 816 KB

Cite this

de Berg, M., & van Wordragen, G. (2023). Improved Bounds for Discrete Voronoi Games. In P. Morin, & S. Suri (Eds.), Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings (pp. 291-308). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 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. editor / Pat Morin ; Subhash Suri. Springer, 2023. pp. 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. in P Morin & S Suri (eds), 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), vol. 14079 LNCS, Springer, pp. 291-308, International Symposium on Algorithms and Data Structures, Montreal, Canada, 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. ed. / Pat Morin; Subhash Suri. Springer, 2023. p. 291-308 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14079 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

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. In Morin P, Suri S, editors, Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings. Springer. 2023. p. 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