Self-improving Algorithms for Geometric Problems

PhD Qualifying Examination


Title: "Self-improving Algorithms for Geometric Problems"

by

Mr. Man Ting WONG


Abstract:

The computation of Convex hulls is a well-known computational geometry problem. 
As many are exposed to planar algorithms to compute convex hulls optimally, 
convex hulls computations can become significantly harder in high dimensions as 
the number of facets of a convex hull no longer linear in size of the input 
points. As points interior of a convex hulls are to be abandoned, only extremal 
points will participate in generating the facets, thus the efficiency of 
removing non-extremal points have implications on the optimality of the 
algorithms.

In this survey we will discuss a few classic algorithms to compute convex 
hulls. Some of them remove non-extremal points in constant time meanwhile some 
others require logarithmic time. The survey follows by introducing the genre of 
self-improving algorithms, where this genre of algorithms has two phases: in 
the training phase the algorithm collects a number of samples in proportion 
with a relatively stabled cardinality of the input points. Subsequently, in the 
limiting phase the algorithm is able to compute the desired geometric structure 
optimally with regard to any comparison-based algorithms. The survey ends with 
proposing a few directions on how to exploit the framework with self-improving 
algorithms.


Date:			Tuesday, 3 December 2019

Time:                  	10:30am - 12:30pm

Venue:                  Room 5506
                         Lifts 25/26

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


**** ALL are Welcome ****