On topological changes in the Delaunay triangulation of moving points

DOI10.1145/2261250.2261252zbMATH Open1275.52021arXiv1304.3671OpenAlexW2092074133MaRDI QIDQ2391707FDOQ2391707

Authors: Natan Rubin 

Publication date: 5 August 2013

Published in: Discrete \& Computational Geometry, Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: Let $P$ be a collection of $n$ points moving along pseudo-algebraic trajectories in the plane. One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a subcubic bound, on the maximum number of discrete changes that the Delaunay triangulation $DT(P)$ of $P$ experiences during the motion of the points of $P$. In this paper we obtain an upper bound of $O(n^{2+eps})$, for any $eps>0$, under the assumptions that (i) any four points can be co-circular at most twice, and (ii) either no triple of points can be collinear more than twice, or no ordered triple of points can be collinear more than once.

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

Recommendations

• On topological changes in the Delaunay triangulation of moving points
• Delaunay-Based Polygon Morphing Across a Change in Topology
• Regular triangulations of dynamic sets of points
• scientific article; zbMATH DE number 1045404
• Queries on Voronoi diagrams on moving points
• Delaunay triangulations of point sets in closed Euclidean \(d\)-manifolds
• scientific article; zbMATH DE number 1225873
• Voronoi diagrams of rigidly moving sets of points
• Voronoi diagrams of moving points in higher dimensional spaces
• Delaunay triangulation of manifolds

zbMATH Keywords

Delaunay triangulationVoronoi diagramcombinatorial complexitykinetic algorithmsmoving pointsdiscrete changes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Title not available (Why is that?)
• Applications of random sampling in computational geometry. II
• Title not available (Why is that?)
• Geometry and topology for mesh generation
• Title not available (Why is that?)
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The overlay of lower envelopes and its applications
• VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE
• Kinetic stable Delaunay graphs
• A kinetic triangulation scheme for moving points in the plane
• A two-dimensional kinetic triangulation with near-quadratic topological changes
• Near-quadratic bounds for the \(L_ 1\) Voronoi diagram of moving points
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• Ready, set, go! The Voronoi diagram of moving points that start from a line
• 3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations

Cited In (5)

• On topological changes in the Delaunay triangulation of moving points
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• A simple, faster method for kinetic proximity problems
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• Stable Delaunay graphs

This page was built for publication: On topological changes in the Delaunay triangulation of moving points

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