An optimal algorithm for closest pair maintenance (extended abstract)
Published 1 January 1995Open access
Sergei Bespamyatnikh
Citations14
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work gives a data structure of size O(n) that maintains a closest pair of S in O(log n) time per insertion and deletion of S, and assumes that the dimension k and the distance metric Lt are fixed.
Abstract
Article Free Access Share on An optimal algorithm for closest pair maintenance (extended abstract) Author: Sergei N. Bespamyatnikh Department of Mathematics and Mechanics, Ural State University, 51 Lenin St., Ekaterinburg 620083, Russia Department of Mathematics and Mechanics, Ural State University, 51 Lenin St., Ekaterinburg 620083, RussiaView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995Pages 152–161https://doi.org/10.1145/220279.220296Published:01 September 1995Publication History 13citation488DownloadsMetricsTotal Citations13Total Downloads488Last 12 Months26Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Keywords
Computer Science
Mathematics of ComputationComputational Geometry--An Introduction.
4,264 Citations1986Mikhail J. Atallah, Franco P. Preparata +1 more
Journal of the ACMAn optimal algorithm for approximate nearest neighbor searching fixed dimensions
2,321 Citations1998Sunil Arya, David M. Mount +3 more
It is shown that it is possible to preprocess a set of data points in real D-dimensional space in O(kd) time and in additional space, so that given a query point q, the closest point of S to S to q can be reported quickly.
Closest-point problems
1,062 Citations1975Michael Ian Shamos, Dan Hoey
The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
Journal of the ACMA decomposition of multidimensional point sets with applications to <i>k</i> -nearest-neighbors and <i>n</i> -body potential fields
555 Citations1995Paul B. Callahan, S. Rao Kosaraju
The notion of a well-separated pair decomposition of points in d-dimensional space is defined and the resulting decomposition is applied to the efficient computation of nearest neighbors and body potential fields.
Lower bounds for algebraic computation trees
525 Citations1983Michael Ben-Or
All the apparently known lower bounds for linear decision trees are extended to bounded degree algebraic decision trees, thus answering the open questions raised by Steele and Yao [20].
Approximate nearest neighbor queries in fixed dimensions
312 Citations1993Sunil Arya, David M. Mount
A practical variant of this algorithm is implemented, and it is shown empirically that for many point distributions this variant of the algorithm finds the nearest neighbor in moderately large dimension significantly faster than existing practical approaches.
Discrete & Computational GeometryAnO(n logn) algorithm for the all-nearest-neighbors Problem
219 Citations1989Pravin M. Vaidya
This work gives anO(n logn) algorithm for the all-nearest-neighbors problem, for fixed dimensionk and fixed metricLq, which is optimal up to a constant factor.
SIAM Journal on ComputingBiased Search Trees
146 Citations1985Samuel W. Bent, Daniel D. Sleator +1 more
Two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations are described.
Divide-and-conquer in multidimensional space
142 Citations1976Jon Bentley, Michael Ian Shamos
A divide-and-conquer technique in multidimensional space is investigated which decomposes a geometric problem into two problems on N/2 points in k dimensions plus a single problem in k−1 dimension to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension.
A decomposition of multi-dimensional point-sets with applications to <i>k</i>-nearest-neighbors and <i>n</i>-body potential fields (preliminary version)
45 Citations1992Paul B. Callahan, S. Rao Kosaraju
The notion of a well-separated pair decomposition of points in d-dimensional space is defined and the resulting decomposition is applied to the efficient computation of nearest neighbors and body potential fields.
Algorithms for dynamic closest pair and n-body potential fields
39 Citations1995Paul B. Callahan, S. Rao Kosaraju
This work presents a general technique for dynamizing certain problems posed on point sets in Euclidean space for any fixed dimension d, and shows how to answer a query for any point x, that returns a constant-size set of points, a subset of which consists of all points in P that have x as a nearest neighbor.
Lecture notes in computer scienceParallel construction of quadtrees and quality triangulations
37 Citations1993Marshall Bern, David Eppstein +1 more
This work describes efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadt trees, and quadtree-based finite element meshes using O(n+k/ log n) processors, where n measures input size and k output size.
Discrete & Computational GeometryMaintaining the minimal distance of a point set in polylogarithmic time
29 Citations1992Michiel Smid
This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.
SciDok (Saarland University and State Library)Maintaining the minimal distance of a point set in less than linear time
25 Citations1990Michiel Smid
New techniques for exact and approximate dynamic closest-point problems
17 Citations1994Sanjiv Kapoor, Michiel Smid
A dynamic data structure is given for this problem having close to linear size and polylogarithmic query and update times and it is shown that a range tree can be used to find an euclidean distance between any query point and its true nearest neighbor.
An optimal algorithm for the on-line closest-pair problem
17 Citations1992Christian Schwarz, Michiel Smid +1 more
Lecture notes in computer scienceShallow interdistance selection and interdistance enumeration
16 Citations2005Jeffrey S. Salowe
A shallow interdistance selection algorithm which takes optimal O(n log n) time and works in any L p metric, and an algorithm which, given a set of n points and an integer k, outputs all interdistances having rank at most k in O( n log n+k) time.
Symposium on Discrete AlgorithmsA unified approach to dynamic point location, ray shooting, and shortest paths in planar maps
14 Citations1993Yi‐Jen Chiang, Franco P. Preparata +1 more
SIAM Journal on ComputingRandomized Data Structures for the Dynamic Closest-Pair Problem
13 Citations1998Mordecai J. Golin, Rajeev Raman +2 more
A new randomized data structure, the sparse partition, is described for solving the dynamic closest-pair problem, using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time.
MPG.PuRe (Max Planck Society)Simple randomized algorithms for closest pair problems
13 Citations1995Mordecai J. Golin, Rajeev Raman +2 more
Symposium on Discrete AlgorithmsRandomized data structures for the dynamic closest-pair problem
11 Citations1993Mordecai J. Golin, Rajeev Raman +2 more
Information and ComputationDynamic Rectangular Point Location, with an Application to the Closest Pair Problem
10 Citations1995Marcel Smid
A linear size data structure is given for the k -dimensional rectangular point location problem, allowing queries to be solved in O ((log n ) k − 1 log log n ) time, and allowing the four update operations to be performed in O((log n) 2 log Log n ) amortized time).
Lecture notes in computer scienceCombine and conquer: A general technique for dynamic algorithms
6 Citations1993Robert Cohen, Roberto Tamassia
This work presents a general technique for dynamizing a significant class of problems whose underlying structure is a computation graph embedded in a tree and supports a complete repertory of dynamic operations in logarithmic time using linear space.
Symposium on Discrete AlgorithmsAn O(n log n log log n) Algorithm for the On-line Closest Pair Problem
6 Citations1992Christian Schwarz, Michiel Smid
The algorithm is based on Bentley's logarithmic method for decomposable searching problems and uses a non-trivial extension of fractional cascading to k -dimensional space.