Actually, this question is asked by D.E Shaw Research.
Design a data structure to store 3-dimension points in a space. This structure needs to be efficient for retrieve, deletion and insertion.
Note: The space is really large, with billions of points in it, while it has a certain size.
My solution is:
- Divide the space into cubes
- Store the cubes in an array
- Store points in a LinkedList in each cube
The following questions are:
- What is the proper number and size of the cube?
- How to retrieve the cube? (hash function, use the size of the space)
- Given a central point with its (x,y,z) coordinate, how to retrieve all the points within a sphere of radius r. (need some calculations)