# 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 $k$ in $R^d$ .  Expected time for $d=2$ in a random $(N,\delta)$ -sequence is $O(k^2 + \log n)$ .  For $d > 2, O(k^{\lceil d/2\rceil + 2} n^{\lceil d/2 \rceil -1})$ .

In the 2-dimensional case, the query time is $O(k \log^2 n)$ and update time is $O(k^2 + \log n)$ .  Similarly for 3-dimensions, query time is $O(k \log^2 n)$ and update time is $O(k^4 n \log^2 n)$ .

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 $O(n)$ time.  To remove points, Ing's 1993 reversion algorithm is used, with worst case $O(n)$ 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 $\Theta(n)$ edges in the worst case, therefore no worst-case-sublinear algorithms exist.  They present an algorithm that is $O(n)$ for both insert and delete, using a V-tree (Voronoi tree) design.

Each leaf of the tree stores a point in the given pointset $S$ .  Internal nodes $x$ store the Voronoi diagram $VOD(sub(x))$ for the subtree rooted at $x$ .  This requires $O(nh)$ storage, where $h$ is the height of the tree, but may be reduced to $O(n \log \log n)$ and preserving linear update time.

Applications

Consider the $k$ -minimum spanning circle problem: Given a planar point set $S=\{(x_j, y_j) | 1 \le j \le n\}$ where $n > k$ , find $k$ circles that every point in $S$ is contained in at least one circle and the largest circle is minimized.