# Monthly Archives: February 2013

## Dynamic Algorithms in Computational Geometry

Dynamic Algorithms in Computational Geometry; Li; date

This is a survey paper of dynamic algorithms available for a variety of geometric problems, including nearest neighbor.  For Voronoi diagrams, Li describes Mumuley's algorithm for diagrams of order 1 to  in  .  Expected time for  in a random  -sequence is  .  For  .

In the 2-dimensional case, the query time is  and update time is  .  Similarly for 3-dimensions, query time is  and update time is  .

Mumuley. Computational Geometry: an introduction through randomized algorithms. 1994, Prentice-Hall Inc.

Filed under Algorithms, Voronoi Diagrams

## Generalized Voronoi Diagram Updating

Improved Updating of Euclidean Distance Maps and Voronoi Diagrams; Lau, Sprunk, Burgard; date

Primarily focuses on the Generalized Voronoi Diagram as used in navigation for robotics.  Diagrams are represented on grid maps.

Filed under Algorithms, Voronoi Diagrams

## Interactive Analysis Using Voronoi Diagrams

Interactive analysis using voronoi diagrams: Algorithms to support dynamic update from a generic triangle-based data structure; Lee, Gahegan; 2002

Describe methods for updating five types of Voronoi diagrams using a data structure that stores the Delaunay triangulation of a given pointset.  For Ordinary Vornoi Diagrams (OVD), edge swapping is used to dynamically insert points in  time.  To remove points, Ing's 1993 reversion algorithm is used, with worst case  time.

Filed under Algorithms, Voronoi Diagrams

## Dynamic Voronoi Diagrams

Dynamic Voronoi Diagrams; Gowda, Kirkpatrick, Lee, Naamad; 1983

First note that dynamically updating a Voronoi diagram by adding or removing one point can change as many as  edges in the worst case, therefore no worst-case-sublinear algorithms exist.  They present an algorithm that is  for both insert and delete, using a V-tree (Voronoi tree) design.

Each leaf of the tree stores a point in the given pointset  .  Internal nodes  store the Voronoi diagram  for the subtree rooted at  .  This requires  storage, where  is the height of the tree, but may be reduced to  and preserving linear update time.

Applications

Consider the  -minimum spanning circle problem: Given a planar point set  where  , find  circles that every point in  is contained in at least one circle and the largest circle is minimized.