Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

DOI10.1016/j.comgeo.2016.04.001zbMath1381.65019OpenAlexW2339879713MaRDI QIDQ680145

Timothy M. Chan, Zahed Rahmati

Publication date: 22 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.04.001

zbMATH Keywords

nearest neighbor searchclosest pair distancekinetic algorithmslinearly moving pointsnearest neighbor distances

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

A clustering-based approach to kinetic closest pair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal partition trees
• Range searching with efficient hierarchical cuttings
• Fast algorithms for collision and proximity problems involving moving geometric objects
• A simple, faster method for kinetic proximity problems
• Approximate k -flat Nearest Neighbor Search
• Approximating extent measures of points
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Higher harmonic resonances in free convection between vertical parallel plates
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Approximate Nearest Line Search in High Dimensions
• Kinetic connectivity for unit disks