A Data Structure and an Algorithm for the Nearest Point Problem
- 1 September 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. SE-9 (5), 631-634
- https://doi.org/10.1109/tse.1983.235263
Abstract
In this paper we present a tree structure for storing points from a normed space whose norm is effectively computable. We then give an algorithm for finding the nearest point from the tree to a given query point. Our algorithm searches the tree and uses the triangle inequality to eliminate searching of the entirety of some branches of the tree whenever a certain predicate is satisfied. Our data structure uses 0(n) for storage. Empirical data which we have gathered suggest that the expected complexity for preprocessing and the search time are, respectively, 0(nlogn) and 0(logn).Keywords
This publication has 9 references indexed in Scilit:
- Optimal Expected-Time Algorithms for Closest Point ProblemsACM Transactions on Mathematical Software, 1980
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- The "Why-Don't-You-Just...?" Barrier in Discrete AlgorithmsThe American Mathematical Monthly, 1979
- The complexity of finding fixed-radius near neighborsInformation Processing Letters, 1977
- Applications of a planar separator theoremPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Convex hulls of finite sets of points in two and three dimensionsCommunications of the ACM, 1977
- Finding nearest neighboursInformation Processing Letters, 1976
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Geometric complexityPublished by Association for Computing Machinery (ACM) ,1975