An optimal algorithm for the on-line closest-pair problem

DOI10.1007/BF01377181zbMath0863.68113OpenAlexW2051390146MaRDI QIDQ1330783

Jack Scott Snoeyink, Michiel H. M. Smid, Christian Schwarz

Publication date: 10 August 1994

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01377181

zbMATH Keywords

centroidsclosest pairamortization

Mathematics Subject Classification ID

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

Related Items (4)

Dynamic Euclidean minimum spanning trees and extrema of binary functions ⋮ Dynamic closest pairs — A probabilistic approach ⋮ Walking around fat obstacles. ⋮ Approximate \(k\)-closest-pairs in large high-dimensional data sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Maintaining the minimal distance of a point set in polylogarithmic time
• ENUMERATING INTERDISTANCES IN SPACE

This page was built for publication: An optimal algorithm for the on-line closest-pair problem