aalto1 untyped-item.component.html
Improved Bounds for Discrete Voronoi Games
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
18
Series
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) ; Volume 14079 LNCS
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.
Description
Funding Information: MdB is supported by the Dutch Research Council (NWO) through Gravitation grant NETWORKS-024.002.003. Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
Other note
Citation
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