Make delicious recipes!

Quadtree, Octree and kd-tree



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 StepLatitudeLongitude
10-360, 0-360
20-180, 0-180
391-180, 0-90
4135-180, 45-90
5135-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(log4N) 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.





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


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

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal