chaveza9 / comparative_analysis_datastructures

This project describes a comparative analysis between KD-Trees and Quadtrees.

Comparative Analysis of Spatial Data Structures

The goal of our project was to compare 2 spatial data structures (Kd-Trees and Quadtrees). This involves a comparison of the amortized analysis of the most basic methods of each of the data structures (find, insert, and delete) with the possibility of implementing methods that are significant to each (such as nearest-neighbor query for kd-trees and quad trees) using randomly generated datasets and different permutations of these.

The implementation methods that this project focuses on are insert and find for the spatial data structures and comparing runtimes. This methods are essential since they can be extrapolated for other methods such as delete or region query. A sample implementation of these mehods was coded for quad trees where the nearest neighbor query and region query was run. The report attached to this repository presents the combined results and methods of the spatial data structures implementations.

In order to run each data structures, the user needs to access the corresponding data structure folder. Each folder contains a separate README file that explains how to run the code