Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions

DOI10.1007/S00454-015-9729-3zbMATH Open1351.68295arXiv1404.4851OpenAlexW2156831926MaRDI QIDQ908209FDOQ908209

Authors: Pankaj K. Agarwal, Haim Kaplan, Natan Rubin, Micha Sharir 

Publication date: 3 February 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let $P$ be a set of $n$ points and $Q$ a convex $k$-gon in ${mathbbR}^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^{4}nlambd{a}_r(n))$ on the number of topological changes experienced by the diagrams throughout the motion; here $lambd{a}_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.

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

Recommendations

• scientific article; zbMATH DE number 219238
• A 2D kinetic triangulation with near-quadratic topological changes
• Voronoi Diagrams of Moving Points
• Voronoi diagrams over dynamic scenes
• A kinetic triangulation scheme for moving points in the plane

zbMATH Keywords

Delaunay triangulationVoronoi diagramconvex distance functionkinetic data structuremoving pointsdiscrete changes

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• CGAL Arrangements and their applications. A step-by-step guide
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Voronoi diagrams and Delaunay triangulations
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• Data Structures for Mobile Data
• On Some Distance Problems in Fixed Orientations
• Title not available (Why is that?)
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Title not available (Why is that?)
• Polyhedral Voronoi diagrams of polyhedra in three dimensions
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Kinetic spanners in \(\mathbb R^{d}\)
• A geometric consistency theorem for a symbolic perturbation scheme
• Kinetic stable Delaunay graphs
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Near-quadratic bounds for the \(L_ 1\) Voronoi diagram of moving points
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stable Delaunay graphs

Cited In (12)

• Title not available (Why is that?)
• Kinetic Polar Diagram
• Title not available (Why is that?)
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Empty squares in arbitrary orientation among points
• Kinetic and dynamic Delaunay tetrahedralizations in three dimensions
• Kinetic stable Delaunay graphs
• 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
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• A 2D kinetic triangulation with near-quadratic topological changes

Uses Software

• CGAL

This page was built for publication: Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions

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