Kinetic stable Delaunay graphs

DOI10.1145/1810959.1810984zbMATH Open1284.68576arXiv1504.06851OpenAlexW2111128036MaRDI QIDQ5405875FDOQ5405875

Authors:

Publication date: 3 April 2014

Published in: Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: Let $P$ be a set of $n$ points in $mathrm{R}^2$, and let $mathrmDT(P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $mathrmDT(P)$ being {it stable}. Defined in terms of a parameter $alpha>0$, a Delaunay edge $pq$ is called $alpha$-stable, if the (equal) angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at least $alpha$. A subgraph $G$ of $mathrmDT(P)$ is called {it $(calpha,alpha)$-stable Delaunay graph} ($mathrmSDG$ in short), for some constant $cge1$, if every edge in $G$ is $alpha$-stable and every $calpha$-stable of $mathrmDT(P)$ is in $G$. We show that if an edge is stable in the Euclidean Delaunay triangulation of $P$, then it is also a stable edge, though for a different value of $alpha$, in the Delaunay triangulation of $P$ under any convex distance function that is sufficiently close to the Euclidean norm, and vice-versa. In particular, a $6alpha$-stable edge in $mathrmDT(P)$ is $alpha$-stable in the Delaunay triangulation under the distance function induced by a regular $k$-gon for $kge2pi/alpha$, and vice-versa. Exploiting this relationship and the analysis in~cite{polydel}, we present a linear-size kinetic data structure (KDS) for maintaining an $(8alpha,alpha)$-$mathrmSDG$ as the points of $P$ move. If the points move along algebraic trajectories of bounded degree, the KDS processes nearly quadratic events during the motion, each of which can processed in $O(logn)$ time. Finally, we show that a number of useful properties of $mathrmDT(P)$ are retained by $mathrmSDG$ of $P$.

Full work available at URL: https://arxiv.org/abs/1504.06851

Recommendations

• Stable Delaunay graphs
• Kinetic pie Delaunay graph and its applications
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Kinetic and dynamic Delaunay tetrahedralizations in three dimensions
• The stability of Delaunay triangulations
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• scientific article; zbMATH DE number 5220265
• A self-stabilizing and local Delaunay graph construction
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Delaunay stability via perturbations

zbMATH Keywords

Delaunay triangulationVoronoi diagramkinetic data structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (15)

• Euclidean minimum spanning trees with independent and dependent geometric uncertainties
• Title not available (Why is that?)
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Kinetic pie Delaunay graph and its applications
• On shape Delaunay tessellations
• A simple, faster method for kinetic proximity problems
• A framework for algorithm stability and its application to kinetic Euclidean MSTs
• Kinetic and dynamic Delaunay tetrahedralizations in three dimensions
• A kinetic triangulation scheme for moving points in the plane
• Static and kinetic geometric spanners with applications
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• A two-dimensional kinetic triangulation with near-quadratic topological changes
• Stable Delaunay graphs
• A 2D kinetic triangulation with near-quadratic topological changes
• Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties

This page was built for publication: Kinetic stable Delaunay graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405875)