Design a data structure to store 3D points.


  • 1
    M

    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:

    1. Divide the space into cubes
    2. Store the cubes in an array
    3. Store points in a LinkedList in each cube

    The following questions are:

    1. What is the proper number and size of the cube?
    2. How to retrieve the cube? (hash function, use the size of the space)
    3. 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)

  • 1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.