Maintaining the minimal distance of a point set in polylogarithmic time

DOI10.1007/BF02187852zbMATH Open0764.68181OpenAlexW2999274412MaRDI QIDQ1189290FDOQ1189290

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

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

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)

Cites Work

• Title not available (Why is that?)
• The design of dynamic data structures
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Title not available (Why is that?)
• Dynamic fractional cascading
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Static and dynamic algorithms for k-point clustering problems
• Title not available (Why is that?)
• 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)