Maintaining the minimal distance of a point set in polylogarithmic time

DOI10.1007/BF02187852MaRDI QIDQ1189290zbMATH OpenOpenAlexFDO

Authors Michiel 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) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The complexity of computing minimum separating polygons
• On the complexity of closest pair via polar-pair of point-sets
• On the complexity of closest pair via polar-pair of point-sets
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• A polynomial time computable metric between points sets
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• A fully polynomial time approximation scheme for the smallest diameter of imprecise points
• A time-space trade-off for triangulations of points in the plane
• Computing the Hausdorff set distance in linear time for any \(L_ p\) point distance
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs

Cites work

• scientific article; zbMATH DE number 432753 (Why is no real title available?)
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 177543 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Dynamic fractional cascading
• Dynamization of order decomposable set problems
• Fractional cascading. I: A data structuring technique
• On the average number of rebalancing operations in weight-balanced trees
• The design of dynamic data structures

Cited in

(12)

• A polynomial time computable metric between points sets
• 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
• scientific article; zbMATH DE number 2149349 (Why is no real title available?)
• Static and dynamic algorithms for k-point clustering problems
• scientific article; zbMATH DE number 1305490 (Why is no real title available?)
• Iterated nearest neighbors and finding minimal polytopes
• Algorithms for proximity problems in higher dimensions
• Dynamic well-spaced point sets
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Dynamic data structures for approximate Hausdorff distance in the word RAM

This page was built for publication: Maintaining the minimal distance of a point set in polylogarithmic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1189290)