Suppose I have a set of two-dimensional points, i.e., S={(y_11, y_12), (y_21, y_22), ..., (y_n1, y_n2)} and a fix point (x_1, x_2). Without calculating the distance between (x_1, x_2) and the points in S, is there any kind of efficient algorithms which can find the closest point (y_i1, y_i2) to (x_1, x_2) in S in terms of Euclidean distance. Is it possible this algorithm can be realized by vector or matrix manipulation? Thank you.
4
-
$\begingroup$ Voronoi diagram. That and computational geometry are good search terms. Gerhard "Ask Me About System Design" Paseman, 2011.02.15 $\endgroup$– Gerhard PasemanFeb 16, 2011 at 3:30
-
1$\begingroup$ The Veroni diagram is useful if you have a large collection of fixed points and are then going to find the nearest one of these fixed points for many other points, but the work to compute the Voroni diagram can't be amortized if you only need to do the nearest neighbor calculation once. $\endgroup$– Brian BorchersFeb 16, 2011 at 3:44
-
$\begingroup$ Brian, indeed. Since the poster has provided little motivation, all I will do is suggest an alternative. The poster will have to judge if the alternative is suitable. If the poster gives more, I will be happy to suggest a better fitting alternative. Gerhard "Will Go Only So Far" Paseman, 2011.02.15 $\endgroup$– Gerhard PasemanFeb 16, 2011 at 4:28
-
$\begingroup$ Without further elaboration, this question does not seem appropriate for MathOverflow. The literal answer to your question is "yes" since you can save a little time by only calculating the squares of distances. This can be implemented easily with MATLAB vector manipulation. $\endgroup$– S. Carnahan ♦Feb 16, 2011 at 9:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Since you haven't assumed anything about the distribution of points in S, any algorithm for this problem must examine all $n$ points, and thus take $\Omega(n)$ time. The straight forward algorithm that simply loops through the points computing the distance from the fixed point to each point in the list and then outputs the closest one is an $O(n)$ algorithm, so it's optimal.
You might be concerned about the cost of the arithmetic operations for computing the distances. On any modern processor, the time for loading these coordinates in from memory is much longer than the time it takes to compute the distance.
I'm trying without success to imagine circumstances under which the simple minded algorithm for this problem would be the bottleneck in any practical program- you're almost certainly doing this as part of a larger computation that requires much more than $O(n)$ time. If that's the case, then you should probably be asking about efficient algorithms for the larger problem rather than trying to optimize this tiny part of your bigger problem.
answered Feb 16, 2011 at 2:53
$\begingroup$
$\endgroup$
answered Feb 16, 2011 at 4:11