Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
86
0
0.0
(
0
)
Added by
Wolfgang Mulzer
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $L_p$-norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $O(n log^3 n)$ storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required $O(n^varepsilon)$ time for an update and $O(log n)$ time for a query [SICOMP, 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $O(n^varepsilon)$ factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph.
rate research
Read More
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.
Given a tesselation of the plane, defined by a planar straight-line graph $G$, we want to find a minimal set $S$ of points in the plane, such that the Voronoi diagram associated with $S$ fits $G$. This is the Generalized Inverse Voronoi Problem (GIVP), defined in cite{Trin07} and rediscovered recently in cite{Baner12}. Here we give an algorithm that solves this problem with a number of points that is linear in the size of $G$, assuming that the smallest angle in $G$ is constant.
A data structure is presented that explicitly maintains the graph of a Voronoi diagram of $N$ point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in $tilde O (N^{3/4})$ expected amortized time, where $tilde O$ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that $Theta(sqrt{N})$ amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.
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.
Given a set $S$ of $m$ point sites in a simple polygon $P$ of $n$ vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for $S$ in $P$. It is known that the problem has an $Omega(n+mlog m)$ time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in $O(n+mlog m)$ expected time. The previous best deterministic algorithms solve the problem in $O(nlog log n+ mlog m)$ time [Oh, Barba, and Ahn, SoCG 2016] or in $O(n+mlog m+mlog^2 n)$ time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of $O(n+mlog m)$ time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
