Can somebody explain why quad trees are needed here? I understand their use with Yelp. However, why is it necessary to use such a convoluted algo when a system like Google Places will take two sets of GPS coordinates and compute the approximate distance and ETA pretty accurately? It appears to me that given the client’s GPS coords or address and the GPS coords of all drivers in a given city, it should not be slow to determine which ones are within a given radius of the customer. In fact, I could see an algo that pings taxis periodically to obtain their coords so you don’t have to do on demand.
Actually, if you ignore ETA, and all you want is distance between two sets of GPS coordinates, you can actually compute the geodesic distance very easily assuming the earth is a perfect sphere.
Let me be more precise. If the taxi drivers in a city are T_i for i 1 through n and the customer is a C, you can call the Google Places API to compute each of the distances distance(T_i, C). This does not seem much slower than taken each of the T_i and figuring out which node in the quad tree is T_i in and the selecting only those that are in certain nodes surrounding the client. Off the top of my head, I don’t see much advantage in using the quad tree. Moreover, you have update the link list in the leaves of the quad tree when a T_i crosses from one tree leave to another.
Am I missing anything here?