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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)$.
