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?

  • 1
    $\begingroup$ Voronoi diagram maybe? It might be an overkill though. $\endgroup$
    – nir shahar
    Sep 22, 2021 at 14:40
  • $\begingroup$ I doubt there is faster way to achieve this than exhaustively testing each point $\endgroup$
    – Nikos M.
    Sep 22, 2021 at 15:10
  • $\begingroup$ @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$. $\endgroup$ Sep 22, 2021 at 16:29
  • $\begingroup$ A related StackOverflow answer. $\endgroup$ Sep 22, 2021 at 16:35
  • 1
    $\begingroup$ Related question: Finding the Voronoi cell a point belongs to $\endgroup$
    – Pål GD
    Sep 22, 2021 at 20:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.