Given the coordinates of the user, locating the user in a region in a map is a very common task. This project is concerned with implementing some point location algorithms that run faster by exploiting the potentially highly uneven access frequencies of different regions in the map. Uneven access frequencies may arise due to different popularities of different regions. For the coming term, we focus on the map being the Voronoi diagram, which means that we try to find the closest facility to a user (e.g., restaurant, hospital, etc).
Knowledge in C++ and GUI is needed. The student needs to be competent in programming.
There are two learning objectives:
1. Gain experience in geometric computation.
2. Learn some advanced algorithms in computational geometry.