Suppose I have a set of twodimensional 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.
closed as too localized by S. Carnahan♦ Feb 16 '11 at 9:59This 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. 


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. 

