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

CHENG Siu Wing
Course type
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