File ClosestPair.h

↰ Parent directory (ADS/geometry)

The closest pair of a set of n >= 2 points of the plane, the two points at the least Euclidean distance, by divide et impera in :math:` O( n log n ) ` time, against the :math:` Theta( n^2 ) ` of the comparison of all the pairs (closestPairBrute()).

Definition (ADS/geometry/ClosestPair.h)

Detailed Description

closestPair() sorts the points by x and splits them at the median x into two halves of n / 2 points, solved recursively; if :math:` delta ` is the smaller of their two distances, a closer pair crossing the split has both points in the strip of width :math:` 2 delta ` about it, and a point of the strip has at most 7 others of the strip within :math:` delta ` above it, since a :math:` delta times 2 delta ` rectangle holds at most 8 points at mutual distances at least :math:` delta ; the strip, sorted by y, is scanned comparing each point with the next ones until their difference in y reaches :math: delta , :math: O( n ) . The sort by y comes from the merge of the halves, as in mergesort, so that :math: T( n ) = 2 T( n / 2 ) + O( n ) = O( n log n ) , which is optimal for the algebraic decision trees, since the closest pair decides whether n numbers are distinct, :math: Omega( n log n ) . The squares of the distances are compared, exactly, with the integers of 64 bits. Rabin’s randomized algorithm, and the grid of Khuller and Matias, solve the problem in :math: O( n ) ` expected time, with the floor function out of the decision tree model.

closestPairSweep(), beyond the book, is the sweep of the plane of Hinrichs, Nievergelt and Schorn with no tree: the points, each made a key of 64 bits ( x , y ), sorted by the radix sort of Namespace ADS [see File Sort.h] in O( n ), and each one compared with those before it while their difference in x is below :math:` delta , the least distance so far (all on squares, exact on 64 bits), a point of the same x ending the scan of its column as soon as the difference in y reaches :math: delta , since the column is sorted by y. A point meets the points in the strip of width :math: delta ` before it, O( 1 ) of them on points spread in the plane, whence O( n ) after the sort; some inputs make the strips full of points far in y: after 16 n comparisons the sweep gives up and starts again along y, and if that fails too the randomized grid of Golin, Raman, Schwarz and Smid solves the problem: the points in a random order, the i-th looked for in the 9 cells around its own of a grid of side :math:` lceil delta_i rceil ` hashed by the cells, each cell with O( 1 ) points of the grid; the grid is built again with the i points when :math:` delta ` falls, which happens with probability at most 2 / i over the random order, whence :math:` sum_i ( 1 + i cdot 2 / i ) = O( n ) ` expected time on any input. The time is thus O( n ) when a sweep succeeds and O( n ) expected always, against the :math:` Omega( n log n ) ` of the algebraic decision trees, which the grid escapes by the floor function.

The contracts [see File Contract.h]: at least two points, coordinates of absolute value at most :math:` 10^9 `, so that the square of a distance fits in 63 bits; the distance found is that of its two points, a postcondition. The functions are defined in ClosestPair.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Esercizi Divide-et-impera

    1. Shamos, D. Hoey, Closest-point problems, 16th Annual Symposium on Foundations of Computer Science, 151-162, 1975, doi:10.1109/SFCS.1975.8

  1. Hinrichs, J. Nievergelt, P. Schorn, Plane-sweep solves the closest pair problem elegantly, Information Processing Letters 26(5), 255-261, 1988, doi:10.1016/0020-0190(88)90150-0

  1. Golin, R. Raman, C. Schwarz, M. Smid, Simple randomized algorithms for closest pair problems, Nordic Journal of Computing 2(1), 3-27, 1995

  1. Khuller, Y. Matias, A simple randomized sieve algorithm for the closest-pair problem, Information and Computation 118(1), 34-37, 1995, doi:10.1006/inco.1995.1049

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions