Dynamic Voronoi diagrams
IEEE Transactions on Information TheoryPublished 1 September 1983
Impa Bennuru Huliyappa Gowda, David Kirkpatrick, D. Lee, Amnon Naamad
Citations70
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new dynamizing technique is introduced whereby n point Voronoi diagrams (both closest and farthest point) can be updated in O(n) time per insertion or deletion, in the worst case.
Abstract
A new dynamizing technique is introduced whereby n point Voronoi diagrams (both closest and farthest point) can be updated in O(n) time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Closest-point problems
1,062 Citations1975Michael Ian Shamos, Dan Hoey
The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.
SIAM Journal on ComputingOptimal Search in Planar Subdivisions
748 Citations1983David Kirkpatrick
This work presents a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely $O(\log n)$ search time with $O(n)$ storage.
SIAM Journal on ComputingApplications of a Planar Separator Theorem
640 Citations1980Richard J. Lipton, Robert E. Tarjan
SIAM Journal on ComputingFinding Minimum Spanning Trees
425 Citations1976David R. Cheriton, Robert E. Tarjan
This paper studies methods for finding minimum spanning trees in graphs and results include relationships with other problems which might lead general lower bound for the complexity of the minimum spanning tree problem.
Geographical AnalysisProperties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane
373 Citations1980David W. Matula, Robert R. Sokal
Information Processing LettersDecomposable searching problems
337 Citations1979Jon Bentley
Transforms for converting a static structure into a dynamic structure, for adding 'range variables' to queries, and for making preprocessing/query time tradeoffs are presented.
ACM Transactions on Mathematical SoftwareOptimal Expected-Time Algorithms for Closest Point Problems
314 Citations1980Jon Bentley, Bruce W. Weide +1 more
Algorithms for solving a number of closest-point problems in k- space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees can be implemented to solve practical problems very efficiently.
SIAM Journal on ComputingBinary Search Trees of Bounded Balance
258 Citations1973J. Nievergelt, Edward M. Reingold
Efficient computation of continuous skeletons
255 Citations1979David Kirkpatrick
An O(n lgn) algorithm is presented for the construction of skeletons of arbitrary n-line polygonal figures that employs a linear time algorithm for the merging of two arbitrary (standard) Voronoi diagrams.
Journal of the ACMTwo-Dimensional Voronoi Diagrams in the <i> L <sub>p</sub> </i> -Metric
229 Citations1980D. T. Lee
Many proximity problems revolving a set of points, such as finding the nearest neighbor of a given point, finding the minimum spamung tree, findmg the smallest circle enclosing the point set, etc., can be solved very efficiently via the Voronoi diagram.
Journal of the ACMThe Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
159 Citations1983Kenneth J. Supowit
Sous l'hypothese que trois points d'entree ne forment pas un triangle isocele, le RNG de n points dans un espace dimension r peut etre trouve en un temps O(n 2 ) pour r≥3.
Journal of AlgorithmsDynamization of order decomposable set problems
42 Citations1981Mark H. Overmars
A method of structuring sets such that the answer to an order decomposable set problem can be maintained with low worst-case time bounds, while objects are inserted and deleted in the set.
Transforming static data structures to dynamic structures
36 Citations1979James B. Saxe, Jon Bentley
This paper studies general methods for converting static structures to dynamic structures (in which all elements are known before any searches are performed) and studies six new data structures that have been developed by applying the transformations.
Information Processing LettersDynamization of decomposable searching problems
36 Citations1980Jan Van Leeuwen, Derick Wood
In the complexity theory of geometric configurations one encounters a fair number of problems for which a very efficient static solution is known, but no alternative to complete reconstruction seems to come to mind when the authors wish to insert or delete even a single point.
ComputingTwo general methods for dynamizing decomposable searching problems
35 Citations1981M.H. Overmars, Jan Van Leeuwen
Two classes of decomposable searching problems are defined and it is shown that both insertions and deletions can be processed efficiently and a merge technique is exploited to obtain better insertion times.
Open CollectionsDynamic problems in computational geometry
4 Citations2010Impa Bennuru Huliyappa Gowda
The p r i n c i p a l techniques are presented, which include merging of s u b s t r u c t u r e s, and the use of e x t r a storage.
Generalization of heaps and its applications
2 Citations1981Amnon Naamad
A data structure called "generalized heap," which is designed primarily to maintain the solutions of a certain group of problems while the data set is changing over time, is introduced.