function nearest = find_closest ( dn, gn, sn, s, g )

%*****************************************************************************80
%
%% find_closest() finds the nearest G point to each S point.
%
%  Discussion:
%
%    Given two sets of points G and S, this function finds, for every
%    s in S, the index of the closest point g in G.
%
%    This procedure would seem to naturally require GN * SN operations,
%    and that is how this function is programmed.  However, for large
%    datasets, this cost can be prohibitive, and there are procedures
%    for preprocessing the dataset G that can greatly reduce this cost.
%
%    Modified in accordance with suggestions by Gene Cliff, 08 July 2010.
%
%    Modified yet again to deal with the special case of DN = 1,
%    15 September 2010.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    15 September 2010
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer DN, the spatial dimension.
%
%    integer GN, the number of cell generators.
%
%    integer SN, the number of sample points.
%
%    real S(SN,DN), the points to be checked.
%
%    real G(GN,DN), the cell generators.
%
%  Output:
%
%    integer NEAREST(SN), the index of the cell generator nearest
%    to the sample point.
%
  ones_k = ones ( gn, 1 );
  nearest = NaN ( sn, 1 );

  for i = 1 : sn
    d1(1:gn,1:dn) = g(1:gn,1:dn) - ones_k * s(i,1:dn);
    d2 = sum ( d1 .* d1, 2 );
    [ min_val, min_loc ] = min ( d2 );
    nearest(i) = min_loc;
  end

  return
end
