Fast Planar Point Location
Project Description

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).

Supervisor
CHENG Siu Wing
Quota
2
Course type
UROP1100
UROP2100
Applicant's Roles

Knowledge in C++ and GUI is needed. The student needs to be competent in programming.

Applicant's Learning Objectives

There are two learning objectives:

1. Gain experience in geometric computation.

2. Learn some advanced algorithms in computational geometry.

Complexity of the project
Moderate