Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiscrete Voronoi Games and $epsilon$-Nets, in Two and Three Dimensions
133
0
0.0
(
0
)
Added by
Jean-Lou De Carufel
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
An n-simplex is said to be n-well-centered if its circumcenter lies in its interior. We introduce several other geometric conditions and an algebraic condition that can be used to determine whether a simplex is n-well-centered. These conditions, together with some other observations, are used to describe restrictions on the local combinatorial structure of simplicial meshes in which every simplex is well-centered. In particular, it is shown that in a 3-well-centered (2-well-centered) tetrahedral mesh there are at least 7 (9) edges incident to each interior vertex, and these bounds are sharp. Moreover, it is shown that, in stark contrast to the 2-dimensional analog, where there are exactly two vertex links that prevent a well-centered triangle mesh in R^2, there are infinitely many vertex links that prohibit a well-centered tetrahedral mesh in R^3.
The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define many variants of Voronoi diagrams depending on the class of objects, the distance functions and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g. k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connexion with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation. Finally, we give some applications of Bregman Voronoi diagrams which are of interest in the context of computational geometry and machine learning.
We discuss discretization of Koenigs nets (conjugate nets with equal Laplace invariants) and of isothermic surfaces. Our discretization is based on the notion of dual quadrilaterals: two planar quadrilaterals are called dual, if their corresponding sides are parallel, and their non-corresponding diagonals are parallel. Discrete Koenigs nets are defined as nets with planar quadrilaterals admitting dual nets. Several novel geometric properties of discrete Koenigs nets are found; in particular, two-dimensional discrete Koenigs nets can be characterized by co-planarity of the intersection points of diagonals of elementary quadrilaterals adjacent to any vertex; this characterization is invariant with respect to projective transformations. Discrete isothermic nets are defined as circular Koenigs nets. This is a new geometric characterization of discrete isothermic surfaces introduced previously as circular nets with factorized cross-ratios.
The geometric $delta$-minimum spanning tree problem ($delta$-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $delta$, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $delta$-minimum bottleneck spanning tree problem ($delta$-MBST), is the problem of finding a degree bounded spanning tree such that the length of the longest edge is minimum. For point sets that lie in the Euclidean plane, both of these problems have been shown to be NP-hard for certain specific values of $delta$. In this paper, we investigate the $delta$-MBST problem in $3$-dimensional Euclidean space and $3$-dimensional rectilinear space. We show that the problems are NP-hard for certain values of $delta$, and we provide inapproximability results for these cases. We also describe new approximation algorithms for solving these $3$-dimensional variants, and then analyse their worst-case performance.
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram $mathcal{V}(S)$ (and several variants thereof) of a set $S$ of $n$ sites in the plane as sites are added. We define a general update operation for planar graphs modeling the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in $mathbb{R}^3$. We show that the amortized number of edge insertions and removals needed to add a new site is $O(sqrt{n})$. A matching $Omega(sqrt{n})$ combinatorial lower bound is shown, even in the case where the graph of the diagram is a tree. This contrasts with the $O(log{n})$ upper bound of Aronov et al. (2006) for farthest-point Voronoi diagrams when the points are inserted in order along their convex hull. We present a semi-dynamic data structure that maintains the Voronoi diagram of a set $S$ of $n$ sites in convex position. This structure supports the insertion of a new site $p$ and finds the asymptotically minimal number $K$ of edge insertions and removals needed to obtain the diagram of $S cup {p}$ from the diagram of $S$, in time $O(K,mathrm{polylog} n)$ worst case, which is $O(sqrt{n};mathrm{polylog} n)$ amortized by the aforementioned result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained at all times and can be traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in $O(log n)$ time, or to determine whether two given sites are neighbors in the Delaunay triangulation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
