 ComputationalGeometry - Maple Programming Help

Home : Support : Online Help : Mathematics : Geometry : Computational Geometry : ComputationalGeometry/ClosestPointPair

ComputationalGeometry

 ClosestPointPair
 determine the closest pair of points in a collection

 Calling Sequence ClosestPointPair(L) ClosestPointPair(L, cutoff=n)

Parameters

 L - list or Array of points with the same dimension n - a positive integer

Description

 • Find the closest pair of points in L using the classic divide and conquer approach. The answer is returned as an expression sequence with two elements: the distance between a closest pair, and a list with the indices of a pair of points that are closest.
 • A value n can be given with the cutoff option to customize when the algorithm switches to a brute force search. The default value of 6 has been found to work very well in most cases. A value greater than half the number of points in L will cause the command to work entirely by brute force search.
 • Setting the infolevel of CompGeomPlot to 4 will cause the command to display a graphical trace of the computation.

Examples

 > $\mathrm{with}\left(\mathrm{ComputationalGeometry}\right):$
 > $\mathrm{ClosestPointPair}\left(\left[\left[0,1\right],\left[2,2\right],\left[1,1\right],\left[4,4\right]\right]\right)$
 ${1}{,}\left[{1}{,}{3}\right]$ (1)
 > $L≔\left[\mathrm{seq}\left(\mathrm{seq}\left(\mathrm{seq}\left(\left[i,j,k\right],i=0..4,0.25\right),j=0..4,0.25\right),k=0..4,0.25\right),\left[1.85,1.85,1.85\right]\right]:$
 > $d,p≔\mathrm{ClosestPointPair}\left(L\right)$
 ${d}{,}{p}{≔}{0.1732050808}{,}\left[{2150}{,}{4914}\right]$ (2)
 > $L\left[p\left[1\right]\right],L\left[p\left[2\right]\right]$
 $\left[{1.75}{,}{1.75}{,}{1.75}\right]{,}\left[{1.85}{,}{1.85}{,}{1.85}\right]$ (3)

Compatibility

 • The ComputationalGeometry[ClosestPointPair] command was introduced in Maple 2019.