Exploiting Query Distribution In Planar Point Location

PhD Thesis Proposal Defence


Title: "Exploiting Query Distribution In Planar Point Location"

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 whether more efficient 
algorithm can be obtained by exploiting the query distributions. In this 
thesis, we study the point location algorithms that exploit the query 
distributions to archive o(log n) query time where n is the number of vertices 
of the given subdivision. Most of the existing algorithms require the query 
distribution is given beforehand. In the scenario that the query distribution 
is not known in advance, we propose a point location algorithm for convex 
subdivision with total running time O(n + OPT) to process any online query 
sequence σ, where OPT is the minimum time to answer σ in S by any 
algorithms that can be modeled as a linear decision tree. We also propose a 
point location algorithm for connected subdivision with total running time 
O(|σ|log log n + n + OPT) to process σ.


Date:			Tuesday, 11 September 2018

Time:                  	2:00pm - 4:00pm

Venue:                  Room 3598
                        (lifts 27/28)

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


**** ALL are Welcome ****