The problem of a pair of nearest points is the problem of computational geometry
- Given n points in a metric space , find a pair of points with the smallest distance between them.
The problem of the nearest points on the Euclidean plane [1] was one of the first geometrical problems that underwent a systematic study from the point of computational complexity of geometric algorithms.
A naive algorithm for finding the distances between all pairs in a space of dimension d and choosing the smallest among them takes O ( n 2 ) time . It turns out that the task can be solved in time. in Euclidean space or L p space of fixed dimension d [2] . In the computation model of an algorithm with time O ( n log n ) is optimal when reducing the from . In a computational model in which it is assumed that the calculated for a constant time, the problem can be solved in time [3] . If we allow the use of randomization together with the floor function, the problem can be solved in O ( n ) time [4] [5] .
Content
Brute force algorithm
A pair of the nearest points can be calculated in O ( n 2 ) time by performing a complete iteration . To do this, you can calculate the distance between all n ( n - 1) / 2 pairs of points, then select the pair with the shortest distance, as shown below.
minDist = infinity for i = 1 to length ( P ) - 1 for j = i + 1 to length ( P ) let p = P [ i ], q = P [ j ] if dist ( p , q ) < minDist : minDist = dist ( p , q ) closestPair = ( p , q ) return closestPair
Planar case
The task can be solved in time. using the recursive “ divide and conquer ” approach, for example, so [1] :
- Sort the points according to their x-coordinates.
- We divide the set of points into two subsets of equal size vertical line .
- We solve the problem recursively on the left and on the right. This results in a left minimum distance. and right minimum distance , respectively.
- Find the minimum distance among pairs of points, of which one point lies to the left of the vertical line, and the other point lies to the right of the straight line.
- The final answer will be the minimum value among , and .
It turns out that step 4 can be performed in linear time. Again, a naive approach would require the calculation of distances for all left / right pairs, i.e. quadratic time. The key observation is based on the following sparseness property of a set of points. We already know that the pair of nearest points are not at a greater distance than . Therefore, for each point p to the left of the dividing line, we must compare the distances to the points that lie in the rectangle with dimensions (dist, 2 ⋅ dist) as shown in the figure. And this rectangle can contain no more than six points, the pairwise distance between which is not less . Thus, it is sufficient to calculate 6 n distances at the 4th step [6] . The recurrence ratio for the number of steps can be written as which can be solved with the help of the main theorem for the recurrence of divide and rule , which gives .
Since the pair of the nearest points define an edge in the Delaunay triangulation and correspond to two adjacent cells in the Voronoi diagram , the pair of the nearest points can be determined in linear time if one of these two structures is given. Calculating the Delaunay triangulation or Voronoi diagrams takes time . These approaches are not effective for dimensions d > 2 , while the divide-and-conquer algorithm can be generalized to runtime. for any constant value of dimension d .
The closest pair dynamic task
for the problem of the pair of nearest points is set as follows:
- If given a dynamic set of objects, find algorithms and data structures to effectively recompute a pair of nearest points each time an object is inserted or deleted.
If the bounding rectangle for all points is known in advance and the floor function with a constant operation time is available, a data structure with the expected memory O ( n ) was proposed that supports the expected time (average time) for inserting and deleting O (log n ) and a constant request time . If the task is modified for a model of an algebraic decision tree, insertion and deletion will take an average time. [7] . It should be noted that the complexity of the above dynamic problem of a pair of nearest points depends exponentially on the dimension d , so the algorithm becomes less suitable for problems of high dimension.
The algorithm for the dynamic problem of a pair of nearest points in the space of dimension d was developed by Sergey Bespamyatnykh in 1998 [8] . Points can be inserted and deleted in O (log n ) time by one point (in the worst case).
See also
- Geographic Information System
- The task of finding the nearest neighbor
- The problem of covering the set
Notes
- ↑ 1 2 Shamos, Hoey, 1972 , p. 151-162.
- ↑ Clarkson, 1983 .
- ↑ Fortune, Hopcroft, 1979 , p. 20-23.
- ↑ Khuller, Matias, 1995 , p. 34-37.
- ↑ Richard Lipton. Rabin Flips a Coin (24 September 2011).
- ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 957-961 33.4: Finding the closest pair of points ..
- ↑ Golin, Raman, Schwarz, Smid, 1998 .
- ↑ Bespamyatnikh, 1998 , p. 175-195.
Literature
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Introduction to Algorithms. - Second Edition. - MIT Press and McGraw-Hill, 2001. - ISBN 0-262-03293-7 .
- Translation: Thomas Kormen, Charles Lazerson, Ronald Rivest, Clifford Stein. Algorithms: construction and analysis . - second edition. - Moscow, St. Petersburg, Kiev: “Williams”, 2005. - ISBN 5-8459-0857-4 BBK 32.973.26-018.2.75.
- Jon Kleinberg, Éva Tardos. Algorithm Design. - Addison Wesley, 2006.
- Translation: John Kleinberg , Eva Tardos . Algorithms. Development and application. - Moscow, St. Petersburg, Nizhny Novgorod, Kiev: Peter, 2016. - (Computer Science Classics). - ISBN 978-5-496-01545-5 BBK 32.973.2-018.
- Michael Ian Shamos, Dan Hoey. Closest-point problems // Proc. 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS). - 1975. - DOI : https://dx.doi.org/10.1109/SFCS.1975.8 10.1109 / SFCS.1975.8 [ Error: Invalid DOI! ] .
- Fortune S., Hopcroft JE A note on Rabin's nearest-neighbor algorithm // Information Processing Letters. - 1979. - Vol. 8 , no. 1 .
- Clarkson KL 24th Annual Symposium on Foundations of Computer Science. - 1983.
- Khuller S., Matias Y. A simple randomized sieve algorithm for the closest-pair problem // Inf. Comput .. - 1995. - V. 118 , no. 1 .
- Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid. Randomized Data Structures For The Dynamic Closest-Pair Problem // SIAM J. Comput. . - 1998. - V. 26 , № 4 . The preliminary version was presented at the symposium “4th Annu. ACM-SIAM Symp. on Discrete Algorithms, 1993, pp. 301–310
- Sergey N. Bespamyatnikh. An Optimal Algorithm for Closest-Pair Maintenance // Discrete Comput. Geom .. - 1998. - Vol. 19
- UCSB Lecture Notes
- rosettacode.org - implemented in multiple programming languages
- Line sweep algorithm for the closest pair problem