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 (Corresponding author), Geert van Wordragen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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
Subtitle of host publication	18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings
Editors	Pat Morin, Subhash Suri
Publisher	Springer
Pages	291-308
Number of pages	18
ISBN (Electronic)	978-3-031-38906-1
ISBN (Print)	978-3-031-38905-4
DOIs	https://doi.org/10.1007/978-3-031-38906-1_20
Publication status	Published - 28 Jul 2023
Event	18th International Symposium on Algorithms and Data Structures, WADS 2023 - Montreal, Canada Duration: 31 Jul 2023 → 2 Aug 2023

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	14079
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Symposium on Algorithms and Data Structures, WADS 2023
Country/Territory	Canada
City	Montreal
Period	31/07/23 → 2/08/23

Funding

Research at Princeton Univ. was partially supported by a gift from Microsoft. Research at Univ. of California, Irvine was supported by NSF Grant 2212129. Supported by the National Science Foundation grant CCF 2046730. Supported by the National Science Foundation grant CCF 2107434. Supported by DFG grant DI 2041/2. Work supported by Independent Research Fund Denmark, grant 9131-00113B. Acknowledgement. The authors thank Merav Parter for raising the question of designing distance sensitivity oracles that require only subquadratic space. This project received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)”). Acknowledgments. This work was supported, in part, by MUR of Italy, under Projects PRIN 20174LF3T8 (AHeAD: Efficient Algorithms for HArnessing Networked Data), and PNRR CN00000013 (National Centre for HPC, Big Data an d Quantum Computing), and by the University of Padova under Project SID 2020 (RATED-X: Resource-Allocation TradEoffs for Dynamic and eXtreme data). Acknowledgments. We thank Bernd Gärtner for his valuable insights and feedback. This research was supported by the Swiss National Science Foundation under project no. 204320. Keywords: Wiener Index · Optimum communication spanning tree · Minimum routing cost spanning tree This work was partially supported by Grant 2016116 from the United States – Israel Binational Science Foundation. Work by P. Carmi and O. Luwisch was partially supported by the Lynn and William Frankel Center for Computer Sciences. Work by J. Mitchell was partially supported by NSF (CCF-2007275) and by DARPA (Lagrange). This work was partially supported by JSPS KAKENHI Grant Numbers JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP21H03397, JP22H05001, JP23K10982. A full version is available at https://arxiv.org/abs/2305.02059. MdB is supported by the Dutch Research Council (NWO) through Gravitation grant NETWORKS-024.002.003. Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University. Tereza Klimoˇsová is supported by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004) and by GACR grant 22-19073S. This work is partially supported by NSF grant CCF 2049010. This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No.RS-2023-00209069). by the Natural Sciences and Engineering Research Council of Canada Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions. Most proofs from Sects. 3 and 4 are omitted. See [6] for full proofs. M. Chrobak—Research partially supported by National Science Foundation grant CCF-2153723. in part by NSF grant CCF- Acknowledgments. We thank the anonymous reviewers for their careful reading and insightful comments. This research is supported in part by Taiwan NSTC Grant 110-2221-E-007-043. This research was supported in part by NSF under Grants CCF-2005323 and CCF-2300356. A full version of this paper is available at http://arxiv.org/abs/2305.09045.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	NETWORKS-024.002.003

Keywords

Competitive facility location
Spatial voting theory
Voronoi games

Access to Document

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

pdfFinal published version, 574 KBLicence: TAVERNE

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, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings (pp. 291-308). (Lecture Notes in Computer Science (LNCS); Vol. 14079). Springer. https://doi.org/10.1007/978-3-031-38906-1_20

@inproceedings{6d4e933253b745698d6005963ee5bc69,

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",

year = "2023",

month = jul,

day = "28",

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

language = "English",

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

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "291--308",

editor = "Pat Morin and Subhash Suri",

booktitle = "Algorithms and Data Structures",

address = "Germany",

note = "18th International Symposium on Algorithms and Data Structures, WADS 2023 ; Conference date: 31-07-2023 Through 02-08-2023",

}

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, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 14079, Springer, pp. 291-308, 18th International Symposium on Algorithms and Data Structures, WADS 2023, Montreal, Canada, 31/07/23. https://doi.org/10.1007/978-3-031-38906-1_20

Improved Bounds for Discrete Voronoi Games. / de Berg, Mark (Corresponding author); van Wordragen, Geert.
Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings. ed. / Pat Morin; Subhash Suri. Springer, 2023. p. 291-308 (Lecture Notes in Computer Science (LNCS); Vol. 14079).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Improved Bounds for Discrete Voronoi Games

AU - de Berg, Mark

AU - van Wordragen, Geert

PY - 2023/7/28

Y1 - 2023/7/28

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 contribution

AN - SCOPUS:85172734846

SN - 978-3-031-38905-4

T3 - Lecture Notes in Computer Science (LNCS)

SP - 291

EP - 308

BT - Algorithms and Data Structures

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

Y2 - 31 July 2023 through 2 August 2023

ER -