Name
Title | ||
|---|---|---|
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions. |
Abstract | ||
|---|---|---|
Abstract Let P be a set of n points and Q a convex k-gon in \({\mathbb {R}}^2\). We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of P, under the convex distance function defined by Q, as the points of P move along prespecified continuous trajectories. Assuming that each point of P moves along an algebraic trajectory of bounded degree, we establish an upper bound of \(O(k^4n\lambda _r(n))\) on the number of topological changes experienced by the diagrams throughout the motion; here \(\lambda _r(n)\) is the maximum length of an (n, r)-Davenport–Schinzel sequence, and r is a constant depending on the algebraic degree of the motion of the points. Finally, we describe an algorithm for efficiently maintaining the above structures, using the kinetic data structure (KDS) framework. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00454-015-9729-3 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Delaunay triangulation,Voronoi diagram,Moving points,Discrete changes,Convex distance function,Kinetic data structure | Topology,Combinatorics,Bowyer–Watson algorithm,Upper and lower bounds,Kinetic data structure,Weighted Voronoi diagram,Voronoi diagram,Mathematics,Bounded function,Pitteway triangulation,Delaunay triangulation | Journal |
Volume | Issue | ISSN |
abs/1404.4851 | 4 | 1432-0444 |
Citations | PageRank | References |
2 | 0.40 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pankaj K. Agarwal | 1 | 5257 | 593.81 |
| Haim Kaplan | 2 | 3581 | 263.96 |
| Natan Rubin | 3 | 92 | 11.03 |
| Micha Sharir | 4 | 8405 | 1183.84 |