On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions

DOI10.1145/2746228zbMATH Open1333.68260arXiv1312.2194OpenAlexW2178793321MaRDI QIDQ2796411FDOQ2796411

Authors: Natan Rubin 

Publication date: 24 March 2016

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: Let $P$ be a collection of $n$ points in the plane, each moving along some straight line at unit speed. We obtain an almost tight upper bound of $O(n^{2+epsilon})$, for any $epsilon>0$, on the maximum number of discrete changes that the Delaunay triangulation $mathbbDT(P)$ of $P$ experiences during this motion. Our analysis is cast in a purely topological setting, where we only assume that (i) any four points can be co-circular at most three times, and (ii) no triple of points can be collinear more than twice; these assumptions hold for unit speed motions.

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

Recommendations

• A kinetic triangulation scheme for moving points in the plane
• A kinetic triangulation scheme for moving points in the plane
• Kinetic stable Delaunay graphs

zbMATH Keywords

computational geometryDelaunay triangulationVoronoi diagramcombinatorial complexitygeometric arrangementskinetic data structuresmoving pointsdiscrete changes

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Title not available (Why is that?)
• Applications of random sampling in computational geometry. II
• Voronoi diagrams and Delaunay triangulations
• Title not available (Why is that?)
• Geometry and topology for mesh generation
• Some dynamic computational geometry problems
• Almost tight upper bounds for lower envelopes in higher dimensions
• 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
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• The overlay of lower envelopes and its applications
• The Partition Technique for Overlays of Envelopes
• 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
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• 3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations
• Stable Delaunay graphs

Cited In (5)

• A kinetic triangulation scheme for moving points in the plane
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Kinetic and dynamic Delaunay tetrahedralizations in three dimensions
• Kinetic stable Delaunay graphs
• A kinetic triangulation scheme for moving points in the plane

Uses Software

• Voronoi

This page was built for publication: On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions

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