Problem: Given a map holding billions of places of interest such as restaurants, theaters, schools, colleges etc.

Design a navigating device such that it will guide a person from location (x,y) to nearest restaurant.

Solution: Suppose initially the map only holds restaurants.
Then the problem is to move from (x,y) to the nearest data-point.
The data-structure for this problem should be chosen such that it is able to quickly scan the space neighboring (x,y) for a potential match.
If the map was single dimension, a binary tree would have been best for this purpose.
How to get logN or better performance for a 2-Dimensional map?

Quadtrees can be used to solve search problems in 2D space.
A quadtree divides a given node into 4 quarters.
So for this case, it will divide the entire map space (360x360 latitude / longitude) into 4 parts initially.
These 4 parts would be (0-180, 0-180) , (181-360, 0-180) , (0-180, 181-360) , (181-360, 181-360)
Each of these nodes would then divide the space further into 4 nodes.

So for the above problem, one first needs to quickly become aware of the person's co-ordinates.
A quad-tree can help do that.
For example, to locate a person having latitude=140, longitude=50, following search would happen:

Tree Traversal Step

Latitude

Longitude

1

0-360,

0-360

2

0-180,

0-180

3

91-180,

0-90

4

135-180,

45-90

5

135-157,

45-67

This is actually very similar to finding something in a 2D grid. In fact, if the granularity
of the data is not very large, a 2D array can actually be used to do this lookup.

So quad-tree allows to limit the search space to one-fourth of the parent's space at each step.
This helps to find the location in O(log_{4}N) time.
However, the next part of the problem is trickier.

Finding restaurants near the person.

This can be done by searching the space surrounding a person's location.
A good solution is to actually create a 2D array with a good-enough precision of latitude and longitude.
For example: the lat-long value can have precision upto say 0.0001
The 2D array can then be coarsely defined as:

Map<PlaceType, List<Place>> mapArray[][];
// Usage:
double latitude;
double longitude;
Map<PlaceType, List<Place>> places = mapArray[(int)latitude*1000][(int)longitude*1000]
List<Place> restaurants = places.get(PlaceType.RESTAURANT);
// Iterate over restaurants to get the places of interest
// Additionally, one can also search the nearby latitude and longitudes

Similarly Octrees divide the space into 8 parts and are usually used for searching in 3D space.
The concept is extended to k dimensions by kd-trees

So the above problem is solved by using a Octree where latitude and longitude are two dimensions and type of location is the third dimension.

Got a thought to share or found a bug in the code? We'd love to hear from you: