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.

Leave a Comment

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.

Leave a Comment

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.

Leave a Comment

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.

Leave a Comment

Filed under Algorithms, Voronoi Diagrams