Part 1: PR Quadtrees and Range Searches

The second part of your project will expand upon the basic functionality implemented in the first part. Commands will require you to insert verified cities into the spatial map, and to delete them from the spatial map. The role of the spatial map is to support range searches where, given a location in 2-d space and a radius, you will find all the cities within that circle, including on the border. These types of operations are allegedly not efficient using the treemap of coordinates.

You will implement the spatial map using a Point Region (PR) quadtree. Here are resources on the PR quadtree and performing a range search on it.

PR quadtree notes, starts on page 43.

Notes on range search in a PR quadtree, starts on page 23.