Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions

preprint2014arXivOpen access

Abstract

Let PP be a set of nn points and QQ a convex kk-gon in R2{\mathbb R}^2. We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of PP, under the convex distance function defined by QQ, as the points of PP move along prespecified continuous trajectories. Assuming that each point of PP moves along an algebraic trajectory of bounded degree, we establish an upper bound of O(k4nλr(n))O(k^4nλ_r(n)) on the number of topological changes experienced by the diagrams throughout the motion; here λr(n)λ_r(n) is the maximum length of an (n,r)(n,r)-Davenport-Schinzel sequence, and rr 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.