Maintaining the minimal distance of a point set in polylogarithmic time

DOI10.1007/BF02187852zbMath0764.68181OpenAlexW2999274412MaRDI QIDQ1189290

Michiel H. M. Smid

Publication date: 26 September 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131205

zbMATH Keywords

dynamic data structureminimal distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Iterated nearest neighbors and finding minimal polytopes, An optimal algorithm for the on-line closest-pair problem, Efficient construction of a bounded-degree spanner with low weight, Dynamic half-space range reporting and its applications, Dynamic Euclidean minimum spanning trees and extrema of binary functions, Static and dynamic algorithms for k-point clustering problems, Algorithms for proximity problems in higher dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Dynamic fractional cascading
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Fractional cascading. I: A data structuring technique
• An O(n log n) algorithm for the all-nearest-neighbors problem
• On the average number of rebalancing operations in weight-balanced trees
• Dynamization of order decomposable set problems