Closest Pair of Points Problem - Cleve Moler on Mathematics and Computing
 

<div class="content">The Closest Pair of Points problem is a standard topic in an algorithms course today, but when I taught such a course fifty years ago, the algorithm was not yet known.

[B]Contents[/B]
[LIST][*][URL="https://www.labfans.com/bbs/#0f62a942-c8a3-4395-8f83-9509ed1dabd0"]California Dreaming[/URL][*][URL="https://www.labfans.com/bbs/#825b1d10-1532-4f6e-8927-6d9e45dbdb49"]Closest Pair of Points[/URL][*][URL="https://www.labfans.com/bbs/#92c53c07-0f81-494a-91a7-c364eb3132ea"]Pairs[/URL][*][URL="https://www.labfans.com/bbs/#05e723c3-e7a0-4091-bb97-463ac017b7e0"]DivCon[/URL][*][URL="https://www.labfans.com/bbs/#387c9a5e-eee6-47d0-be8a-6ea3d8d95f8f"]Center[/URL][*][URL="https://www.labfans.com/bbs/#53330f5c-f9a0-4060-ba34-e5e98e1c9ed4"]Complexity[/URL][*][URL="https://www.labfans.com/bbs/#5d10f4df-79d5-46b8-9375-01260abdba40"]Timing[/URL][*][URL="https://www.labfans.com/bbs/#4de823af-8e67-4218-a471-d8def3204d38"]Software[/URL][*][URL="https://www.labfans.com/bbs/#0dc6f3e8-7d3a-4381-8d34-13514fb2cad1"]References[/URL][/LIST][B]California Dreaming[/B]

Imagine you are driving a car on the Harbor Freeway in southern California with typical Los Angeles traffic conditions. Among the many things you might want to know is which pair of vehicles is nearest each other.

This is an instance of the Closest Pair of Points problem:
[LIST][*]Given the location of n points in the plane, which pair of points is closest to each other?[/LIST][IMG]https://blogs.mathworks.com/cleve/files/traffic.png[/IMG]

[B]Closest Pair of Points[/B]

It is convenient to represent the points by a vector of complex values. The distance between points z(k) and z(j) is then

d = abs(z(k) - z(j))Here are a few points in the unit square. The closest pair is highlighted.

[IMG]https://blogs.mathworks.com/cleve/files/pairs.png[/IMG]

[B]Pairs[/B]

The first algorithm you might think of computes the distance between all possible pairs of points and finds the minimum. This is a brute force approach that requires only a few lines of code.

function d = Pairs(z) % Pairs. % d = Pairs(z) is the minimum distance between any two elements % of the complex vector z. n = length(z); d = Inf; for k = 1:n for j = k+1:n if abs(z(k) - z(j)) < d d = abs(z(k) - z(j)); end end endend[B]DivCon[/B]

DivCon stands for Divide and Conquer. In outline, the steps are:
[LIST][*]Divide the set of points into two halves.[/LIST][LIST][*]Recursively, find the closest pair in each half.[/LIST][LIST][*]Consider the case when the closest pair has one point in each half.[/LIST][LIST][*]Terminate the recursion with sets of two or three points.[/LIST]function d = DivCon(z,sorted) % DivCon. % d = DivCon(z) is the minimum distance between any two elements % of the complex vector z. % % d = DivCon(z,true) is a recursive call with ascending real(z). n = length(z); if n

[url=https://blogs.mathworks.com/cleve/2024/03/28/closest-pair-of-points-problem/?s_tid=feedtopost]More...[/url]