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

DOI10.1016/J.COMGEO.2016.04.001MaRDI QIDQ680145zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• A clustering-based approach to kinetic closest pair
• Approximate $k$-Nearest Neighbor Graph on Moving Points
• A Clustering-Based Approach to Kinetic Closest Pair
• New Techniques for Exact and Approximate Dynamic Closest-Point Problems

Cites work

• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 6469174 (Why is no real title available?)
• A simple, faster method for kinetic proximity problems
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximate \(k\)-flat nearest neighbor search
• Approximate nearest line search in high dimensions
• Approximating extent measures of points.
• Fast algorithms for collision and proximity problems involving moving geometric objects
• Higher harmonic resonances in free convection between vertical parallel plates
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic connectivity for unit disks
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Optimal partition trees
• Range searching with efficient hierarchical cuttings

Cited in

(4)

• Maintaining approximate extent measures of moving points
• Approximate $k$-Nearest Neighbor Graph on Moving Points
• People mover's distance: class level geometry using fast pairwise data adaptive transportation costs
• A clustering-based approach to kinetic closest pair

This page was built for publication: Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

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