An all-round sweep algorithm for 2-dimensional nearest-neighbor problems

DOI10.1007/BF01178779MaRDI QIDQ1203723zbMATH OpenOpenAlexFDO

Authors Klaus Hinrichs, Jurg Nievergelt, Peter Schorn

Publication date 22 February 1993

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

nearest-neighbor problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4074476
• A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects
• An O(n log n) algorithm for the all-nearest-neighbors problem
• A nearest neighbor sweep circle algorithm for computing discrete Voronoi tessellations
• A new plane-sweep algorithm for the K-closest-pairs query
• A practical approach to the 2D incremental nearest-point problem suitable for different point distributions
• A plane-sweep algorithm for finding a closest pair among convex planar objects
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• scientific article; zbMATH DE number 4060717

Cites work

• A sweepline algorithm for Voronoi diagrams
• An O(n log n) algorithm for the all-nearest-neighbors problem
• scientific article; zbMATH DE number 53811 (Why is no real title available?)

Cited in

(8)

• Expected time analysis for Delaunay point location
• An efficient \(O(1)\) time 3D all nearest neighbor algorithm from image processing perspective
• scientific article; zbMATH DE number 4074476 (Why is no real title available?)
• A low arithmetic-degree algorithm for computing proximity graphs
• A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects
• scientific article; zbMATH DE number 5046292 (Why is no real title available?)
• A sweep algorithm and its implementation: The all-nearest-neighbors problem revisited
• On the symmetric angle-restricted nearest neighbor problem

This page was built for publication: An all-round sweep algorithm for 2-dimensional nearest-neighbor problems

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