closest_point_brute

closest_point_brute, an Octave code which uses brute force to find the nearest of a set of N points in D dimensions to a given test point. This is sometimes called a nearest neighbor calculation.

Licensing:

The information on this web page is distributed under the MIT license.

Languages:

closest_point_brute is available in a C version and a C++ version and a Fortran77 version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Programs:

closest_point_brute_test

cvt, an Octave code which computes elements of a Centroidal Voronoi Tessellation (CVT).

nearest_interp_1d, an Octave code which interpolates a set of data using a piecewise constant interpolant defined by the nearest neighbor criterion.

References:

1. Sunil Arya, David Mount, Nathan Netanyahu, Ruth Silverman, Angela Wu,
   An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions,
   Journal of the ACM,
   Volume 45, Number 6, November 1998, pages 891-923.
2. Jon Bentley, Bruce Weide, Andrew Yao,
   Optimal Expected Time Algorithms for Closest Point Problems,
   ACM Transactions on Mathematical Software,
   Volume 6, Number 4, December 1980, pages 563-580.
3. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.

Source Code:

• closest_point_brute.m, the source code.
• closest_point_brute2.m, a calculation which, for each sample point, uses the MATLAB commands repmat() and min(), hoping for faster execution.
• closest_point_brute3.m, a calculation which, for each sample point, computes the distance vector using matrix algebra.