Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications
- PDF / 1,183,417 Bytes
- 67 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 218 Views
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications Haim Kaplan1 · Wolfgang Mulzer2 Micha Sharir1
· Liam Roditty3 · Paul Seiferth2 ·
Received: 4 June 2019 / Revised: 31 March 2020 / Accepted: 12 August 2020 / Published online: 22 September 2020 © The Author(s) 2020
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 log3 n) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required O(n ε ) 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 ε ) 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. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random
Editor in Charge: János Pach In loving memory of Ricky Pollack, one of the founding fathers of the field, and a dear friend. A preliminary version appeared as [35]. Work by Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth has been supported by Grants 1161/2011 and (with Micha Sharir) 1367/2016 from the German–Israeli Science Foundation. Work by Haim Kaplan has also been supported by Grants 822-10 and 1841-14 from the Israel Science Foundation, and by the Israeli Centers for Research Excellence (I-CORE) program (Center No. 4/11). Work by Wolfgang Mulzer and Paul Seiferth has also been supported by grant MU/3501/1 from Deutsche Forschungsgemeinschaft (DFG) and by ERC StG 757609. Work by Micha Sharir has been supported by Grant 2012/229 from the U.S.–Israel Binational Science Foundation, by Grants 892/13 and 260/18 from the Israel Science Foundation, by the Israeli Centers for Research Excellence (I-CORE) program (Center No. 4/11), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Extended author information available on the last page of the article
123
Discrete & Computational Geometry (2020) 64:838–904
839
sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate al
Data Loading...
