The gravity laws were repealed several decades ago, and people are no longer limited to surface travel; thus, there are many flight docks on and above the planet's surface where tourists can park their rented flyers and go sightseeing. Your job is to handle traffic management on the planet as an increasing number of tourists visit every year. You are responsible for approving straight-line routes between various docks, as well as identifying new sites of interest. You are also responsible for helping tourists plan their trips- helping to find routes that give the best fly-by views of various off-route attractions.
In order to streamline your work you have decided to develop advanced software to help with these tasks.
The assignment is to be done in four segments, with the parts specified below. Part 1 asks you to construct a B+ tree to contain flight docks, to set up an adjacency list to store approved paths between the flight docks, and to build command interpreter to be used in this and later parts. You will also create a k-d tree of order 3 to index the docks based on coordinate. In part 2 you will add the ability to remove docks from the B+ tree. You will also begin testing the PR quadtree 2 dimensional spatial data structure to map the surface level of the planet, which has the highest concentration of docks.
For Part 3 you will replace the PR quadtree with PM1 quadtree in order to analyze your flights along with the docks. For part four you will use an array of PM1 quadtrees to do a simplified map of flights in 3 dimensional space. Somewhere in there you will use your graph to implement some algorithms like shortest path and minimum spanning tree. More on future parts later.