2
$\begingroup$

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 points, calculate the distance 800 times and find the smallest value. But I want to make more efficient algorithm that doesn't execute 800 times due to that it might be sorted in a certain order before searching. That is, if the points is put in a certain order, Could you recommend some notions?

$\endgroup$
1
$\begingroup$

So, if I understand correctly, you have a set $S$ of points in some space (do you have a specific dimension ?), and a point $x$, and you want to find the point of $S$ that is the closest to $x$ ?

If this is indeed what you are trying to do, have a look at K-d trees and Voronoï tesselation. These methods are based on space partitioning to make queries faster.

$\endgroup$
1
$\begingroup$

In addition to GBat's answer, you can also take a look at binary space partitioning (BSP), like $k$-d tree it needs precomputation beforehand, but once the structure is created, each search can be done in $O(\log n)$.

$\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.