A survey on distribution-sensitive point location algorithms

PhD Qualifying Examination


Title: "A survey on distribution-sensitive point location algorithms"

by

Mr. Man Kit LAU


Abstract:

Planar point location problem is a classical problem in computational 
geometry. Several point location algorithms are known that achieve the 
optimal query times asymptotically in worst-case. However, there is still 
a lot of research on this topic. In many applications, certain regions in 
a planar subdivision are more frequently queried. This raises the question 
of where more efficient algorithm can be obtained by exploiting the query 
distributions. In this survey, we cover several distribution-sensitive 
planar point location algorithms and describe their crucial ideas. Some 
constraints and possible future research directions for 
distribution-sensitive planar point location algorithms are discussed.


Date:			Thursday, 12 February 2015

Time:                  	2:00pm - 4:00pm

Venue:                  Room 3494
                         Lifts 25/26

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Cunsheng Ding (Chairperson)
 			Dr. Sunil Arya
 			Dr. Ke Yi


**** ALL are Welcome ****