ﻻ يوجد ملخص باللغة العربية
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.
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
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 (GIV
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 suppo
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 varian
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. Previ