Computer Science – Computational Geometry
Scientific paper
2011-04-04
Computer Science
Computational Geometry
A preliminary version appeared in Proc. SoCG 2010
Scientific paper
We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set $P$ of $n$ moving points in the plane, along algebraic trajectories of constant description complexity. Since the best known upper bound on the number of topological changes in the full $\DT$ is nearly cubic, we seek to maintain a suitable portion of it that is less volatile yet retains many useful properties. We introduce the notion of a stable Delaunay graph, which is a dynamic subgraph of the Delaunay triangulation. The stable Delaunay graph (a) is easy to define, (b) experiences only a nearly quadratic number of discrete changes, (c) is robust under small changes of the norm, and (d) possesses certain useful properties. The stable Delaunay graph ($\SDG$ in short) is defined in terms of a parameter $\alpha>0$, and consists of Delaunay edges $pq$ for which the angles at which $p$ and $q$ see their Voronoi edge $e_{pq}$ are at least $\alpha$. We show that (i) $\SDG$ always contains at least roughly one third of the Delaunay edges; (ii) it contains the $\beta$-skeleton of $P$, for $\beta=1+\Omega(\alpha^2)$; (iii) it is stable, in the sense that its edges survive for long periods of time, as long as the orientations of the segments connecting (nearby) points of $P$ do not change by much; and (iv) stable Delaunay edges remain stable (with an appropriate redefinition of stability) if we replace the Euclidean norm by any sufficiently close norm. In particular, we can approximate the Euclidean norm by a polygonal norm (namely, a regular $k$-gon, with $k=\Theta(1/\alpha)$), and keep track of a Euclidean $\SDG$ by maintaining the full Delaunay triangulation of $P$ under the polygonal norm. We describe two kinetic data structures for maintaining $\SDG$. Both structures use $O^*(n)$ storage and process $O^*(n^2)$ events during the motion, each in $O^*(1)$ time.
Agarwal Pankaj K.
Gao Jie
Guibas Leonidas J.
Kaplan Haim
Koltun Vladlen
No associations
LandOfFree
Kinetic Stable Delaunay Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Kinetic Stable Delaunay Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kinetic Stable Delaunay Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-318370