An optimal algorithm for the all-nearest-neighbors problem

No abstract is available for this paper.

• Publication year

  1986

• Venue

  27th Annual Symposium on Foundations of Computer Science (sfcs 1986)

• Publication date

  1986-10-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.1986.8
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lower bounds for algebraic computation trees

  1983cited by this paper
• Fast algorithms for the all nearest neighbors problem

  1983cited by this paper
• Multidimensional divide-and-conquer

  1980cited by this paper
• Optimal Expected-Time Algorithms for Closest Point Problems

  1980cited by this paper

• ParSCL: A Parallel and Distributed Framework to Process All Nearest Neighbor Queries on a Road Network

  2023cites this paper
• Parallel Nearest Neighbors in Low Dimensions with Batch Updates

  2021cites this paper
• Nearest Neighbor Dirichlet Mixtures

  2020cites this paper
• An O(log⁡n) query time algorithm for reducing ϵ-NN to (c, r)-NN

  2020cites this paper
• A True O(n log{n}) Algorithm for the All-k-Nearest-Neighbors Problem

  2019cites this paper
• An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with O(logn) Query Time

  2018influential citation
• Scalable Algorithms for Data and Network Analysis

  2016cites this paper
• Efficient Construction of Spanners in $d$-Dimensions

  2013cites this paper
• Geometric Approximation Algorithms

  2011cites this paper
• Well-separated pair decomposition

  2011cites this paper
• A near optimal algorithm for finding Euclidean shortest path in polygonal domain

  2010cites this paper
• Chapter 3 Well Separated Pairs Decomposition

  2008cites this paper
• Computer Science Problems in Astrophysical Simulation

  2007cites this paper
• Scalable machine learning for massive datasets: Fast summation algorithms

  2007cites this paper
• A Disc-based Approach to Data Summarization and Privacy Preservation

  2006cites this paper
• Improved fast Gauss transform with variable source scales

  2006cites this paper
• Fast computation of sums of Gaussians

  2006cites this paper
• Well Separated Pairs Decomposition

  2005cites this paper
• Fast Computation of Sums of Gaussians in High Dimensions

  2005cites this paper
• Fast construction of nets in low dimensional metrics, and their applications

  2004cites this paper
• An Optimal Algorithm for Closest-Pair Maintenance

  1998cites this paper
• Improved Approximation Schemes for Geometrical Graphs Via Spanners and Banyans

  1998cites this paper
• Tree data structures for N-body simulation

  1996cites this paper
• Algorithms for dynamic closest pair and n-body potential fields

  1995cites this paper
• Dealing with higher dimensions: the well-separated pair decomposition and its applications

  1995influential citation
• A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

  1995influential citation
• A Dynamic Separator Algorithm

  1993cites this paper
• Optimal parallel all-nearest-neighbors using the well-separated pair decomposition

  1993cites this paper
• A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

  1992cites this paper
• A distribution-free technique to estimate the order of markovian dependence using entropy

  1990cites this paper
• Cell Complexes and Lower Bounds in Computational Geometry

  1990cites this paper
• Approximate minimum weight matching on points ink-dimensional space

  1989cites this paper
• Optimal algorithms for approximate clustering

  1988cites this paper
• A new class of heuristic algorithms for weighted perfect matching

  1988cites this paper
• A Sweep Algorithm and its Implementation: The All-Nearest-Neighbors Problem Revisited

  1988cites this paper
• A Sweep Algorithm for the All-Nearest-Neighbors Problem

  1988cites this paper
• Plane-Sweep Solves the Closest Pair Problem Elegantly

  1988cites this paper
• Algorithms in Combinatorial Geometry

  1987cites this paper
• Picture Processing: 1986

  1987cites this paper