Quadtree, Octree and kd-tree - PrismoSkills
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:
Read full article from Quadtree, Octree and kd-tree - PrismoSkills
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:
Read full article from Quadtree, Octree and kd-tree - PrismoSkills
