Discrete Voronoi games and -nets, in two and three dimensions

DOI10.1016/J.COMGEO.2016.02.002zbMATH Open1378.91008arXiv1501.04843OpenAlexW1562300282MaRDI QIDQ679740FDOQ679740

Authors: Aritra Banik, Jean-Lou De Carufel, Anil Maheshwari, Michiel Smid 

Publication date: 19 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: The one-round discrete Voronoi game, with respect to a $n$-point user set $U$, consists of two players Player 1 ($mathcal{P}_1$) and Player 2 ($mathcal{P}_2$). At first, $mathcal{P}_1$ chooses a set of facilities $F_1$ following which $mathcal{P}_2$ chooses another set of facilities $F_2$, disjoint from $F_1$. The payoff of $mathcal{P}_2$ is defined as the cardinality of the set of points in $U$ which are closer to a facility in $F_2$ than to every facility in $F_1$, and the payoff of $mathcal{P}_1$ is the difference between the number of users in $U$ and the payoff of $mathcal{P}_2$. The objective of both the players in the game is to maximize their respective payoffs. In this paper we study the one-round discrete Voronoi game where $mathcal{P}_1$ places $k$ facilities and $mathcal{P}_2$ places one facility and we have denoted this game as $VG(k,1)$. Although the optimal solution of this game can be found in polynomial time, the polynomial has a very high degree. In this paper, we focus on achieving approximate solutions to $VG(k,1)$ with significantly better running times. We provide a constant-factor approximate solution to the optimal strategy of $mathcal{P}_1$ in $VG(k,1)$ by establishing a connection between $VG(k,1)$ and weak $epsilon$-nets. To the best of our knowledge, this is the first time that Voronoi games are studied from the point of view of $epsilon$-nets.

Full work available at URL: https://arxiv.org/abs/1501.04843

Recommendations

• The 1-dimensional discrete Voronoi game
• The discrete Voronoi game in \(\mathbb{R}^2\)
• Optimal strategies for the one-round discrete Voronoi game on a line
• Optimal strategies for the one-round discrete Voronoi game on a line
• Two-round discrete Voronoi game along a line

zbMATH Keywords

facility location\(\epsilon\)-netsminimum \(k\)-enclosing diskVoronoi games

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) 2-person games (91A05) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Competitive Location Models: A Framework and Bibliography
• Computing a centerpoint of a finite planar set of points in linear time
• Existence theory for spatially competitive network facility location models
• Covering a sphere by equal circles, and the rigidity of its graph
• Fast algorithms for computing the smallest \(k\)-enclosing circle
• The Principle of Minimum Differentiation Reconsidered: Some New Developments in the Theory of Spatial Competition
• Facility location problems in the plane based on reverse nearest neighbor queries
• Competitive spatial models
• The one-round Voronoi game
• Optimal strategies for the one-round discrete Voronoi game on a line
• Computing the smallest \(k\)-enclosing circle and related problems
• An optimal extension of the centerpoint theorem
• On Approximating the Depth and Related Problems
• Min-Max payoffs in a two-player location game
• On the continuous Weber and k -median problems (extended abstract)
• Title not available (Why is that?)
• Optimal strategies for the one-round discrete Voronoi game on a line
• Title not available (Why is that?)
• Static and Dynamic Algorithms for k-Point Clustering Problems
• Improved bounds on weak ε-nets for convex sets

Cited In (6)

• The (1|1)-Centroid Problem in the Plane with Distance Constraints
• Geometric spanner games
• The discrete Voronoi game in \(\mathbb{R}^2\)
• The one-round multi-player discrete Voronoi game on grids and trees
• Improved bounds for discrete Voronoi games
• The 1-dimensional discrete Voronoi game

This page was built for publication: Discrete Voronoi games and \(\epsilon\)-nets, in two and three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679740)