Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions

DOI10.1007/S00454-015-9729-3MaRDI QIDQ908209zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(14)

• scientific article; zbMATH DE number 1617271 (Why is no real title available?)
• Kinetic Polar Diagram
• scientific article; zbMATH DE number 5220265 (Why is no real title available?)
• Empty squares in arbitrary orientation among points
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Kinetic and dynamic Delaunay tetrahedralizations in three dimensions
• Kinetic geodesic Voronoi diagrams in a simple polygon
• Kinetic stable Delaunay graphs
• A two-dimensional kinetic triangulation with near-quadratic topological changes
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• Stable Delaunay graphs
• Largest similar copies of convex polygons in polygonal domains
• Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications
• A 2D kinetic triangulation with near-quadratic topological changes

Describes a project that uses

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)