# Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this route. So basically I am calculating the distance to each point on the route and get the minimum value. But I have to do this many times. If route has n points and there are m coordinates whose distance to the route must be calculated then complexity is m*n. I was just wondering if there could be a smarter way to this this?

• Voronoi diagram maybe? It might be an overkill though. Sep 22, 2021 at 14:40
• I doubt there is faster way to achieve this than exhaustively testing each point Sep 22, 2021 at 15:10
• @NikosM. In $1$-$D$, the problem can be solved in $O((m+n) \log n)$ time. So, I hope there should be better algorithms in $2$-$D$. Sep 22, 2021 at 16:29
• A related StackOverflow answer. Sep 22, 2021 at 16:35
• Related question: Finding the Voronoi cell a point belongs to Sep 22, 2021 at 20:36