GEOMETRIC MATCHING PROBLEMS

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "GEOMETRIC MATCHING PROBLEMS"

By

Miss Juyoung YON


Abstract

In many applications in computer graphics, computer vision, pattern 
recognition, or other related fields, shape matching plays a key role. In 
this thesis we consider several shape matching problems and give 
algorithms to solve them.

First, we introduce an approximate version of the largest common point set 
problem. The largest common point set problem is a standard problem in 
pattern matching. For two given point sets, we want to find a 
transformation that matches maximum subsets of the two point sets under a 
certain metric. Our algorithm works in the plane and we assume that point 
sets move under translations.

Second, we present an approximation algorithm to return a rigid motion of 
three-dimensional Euclidean space for two given convex polyhedra such that 
the volume of the overlap of the polyhedra is maximized. We apply an 
existing algorithm for translations for many sampled candidate rotations. 
The challenge is to deal with three-dimensional rotations.

Last, we explore convex polytope matching problem with respect to the 
volume of the symmetric difference metric. We prove that the function of 
the volume of the symmetric difference is convex and therefore we can 
apply convex programming to our problem. We give necessary and sufficient 
conditions for local minima of the function.


Date:			Tuesday, 19 May 2015

Time:			11:00am - 1:00pm

Venue:			Room 3598
 			Lifts 27/28

Chairman:		Prof.  Kai Tang (MAE)

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Otfried Cheong (Supervisor, KAIST)
 			Prof. Sunil Arya
 			Prof. Ke Yi
 			Prof. Ajay Joneja (ECE)
 			Prof. Takeshi Tokuyama (Tohoku Univ.)


**** ALL are Welcome ****