Finding which vehicles are inside a specified radius

Question

The problem I'm tackling is as follows:

We have a system with thousands of drivers sending their location data to our back-end services. The problem is given a location (lat, long) and a radius to find which vehicles/drivers are inside the circle.

The obvious and easy answer to this problem is a brute force approach: Take every driver's last location and calculate the distance between the driver's vehicle and the center point, it either resides in the circle or not.

However, I believe this approach is not the most scalable and efficient solution especially when we are talking about thousands of queries like this, the system might get overwhelmed.

So my question is what are some better approaches? are there better algorithms? are there any third-party tools/technologies to help me(such as PostGIS etc)?

Thanks for your attention

This isn't a purely algorithmic question; system design concepts and ideas are also involved since scale and other factors are considered. — Abhinav Mathur, Jul 25 '22 at 06:13
using a [K-d tree](https://en.wikipedia.org/wiki/K-d_tree) could be enough here — Alois Christen, Jul 25 '22 at 08:00
Depending on your design, it is a pretty simple task for PostGIS, e.g. with [ST_DWithin](https://stackoverflow.com/a/51889638/2275388) — Jim Jones, Jul 25 '22 at 14:17

score 0 · Answer 1 · answered Jul 25 '22 at 10:17

Consider using a kD-tree (k=2) or a vantage-point-tree.

Anyway, as the vehicles constantly move, you should keep the old positions (when the tree was built) as well as the current positions and perform a search with extra allowance. Then periodically rebuild the tree.

If a rebuild costs O(N Log N) and M queries cost O(M Log N), you are winning against the exhaustive solution O(MN) by a factor approximately (Log N)/M + (Log N)/N.

Finding which vehicles are inside a specified radius

1 Answers1