Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Voronoi diagram. That and computational geometry are good search terms. Gerhard "Ask Me About System Design" Paseman, 2011.02.15 –  Gerhard Paseman Feb 16 '11 at 3:30
1  
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. –  Brian Borchers Feb 16 '11 at 3:44
    
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 –  Gerhard Paseman Feb 16 '11 at 4:28
    
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. –  S. Carnahan Feb 16 '11 at 9:59
add comment

closed as too localized by S. Carnahan Feb 16 '11 at 9:59

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.