0
$\begingroup$

So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me.

I need to write code that will take in a point, $p_0$, and will find the point $(p_1, p_2, p_3\ldots)$ closet to $p_0$. This will of course be found my minimizing $R$ in $R^2 = (x - x_0)^2 + (y - y_0)^2$.

I could implement this easily if I linearly search the list of points each time (always $O(n)$ complexity). However, I would prefer something that could be an average of $\log(n)$ complexity. Does anyone have a suggestion on a search algorithm?

$\endgroup$
  • 1
    $\begingroup$ Do you wish to test several points $p_0$ with the same set of points $p_1,p_2,\ldots$? In that case, we can spend $O(n\log n)$ time to build a data structure such that all later queries will take $O(\log n)$. Otherwise, you'll have to spend linear time at least. $\endgroup$ – Discrete lizard Feb 2 '18 at 14:44
  • $\begingroup$ en.wikipedia.org/wiki/K-d_tree $\endgroup$ – D.W. Feb 2 '18 at 16:54
2
$\begingroup$

If we make no assumptions on input and want an exact answer to the question what the minimum distance is to $p_0$, any algorithm must take at least $\Omega(n)$ time in the worst case. To see this, suppose $p_0$ is in your input points. In the worst case, the final point we see in our list is this point! So we must inspect all our input points and hence take $\Omega(n)$ time.

For the same reason, an approximation algorithm must also use $\Omega(n)$ time, as the difference in distance to $p_0$ between the inspected points in the list and the points we haven't inspected yet may be arbitrarily large.

The only way I see to be faster than linear is to take a random sample from your list to get the right answer with a certain probability. However, I think the running time would heavily depend on the probability you would want in the list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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