Geometric Matching Problems

PhD Thesis Proposal 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 various kinds of shape matching problems and give 
a possible direction to solve those problems.

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 maximal subsets of each point sets under a 
certain metric. Our algorithm works in the plane and we assume that point 
sets move under translations. Bottleneck distance is used for the 
similarity measure between point sets to overcome a drawback of Hausdorff 
distance.

Second, we present an approximation algorithm to return a rigid motion of 
3-dimensional Euclidean space for two given convex polyhedra such that the 
volume of the overlap of the polyhedra is maximized. We applied the 
existing algorithm for translations for each sampled candidate rotations. 
The challenge of this problem is dealing with 3-dimensional rotations.

Last, we explore convex polygon approximation problems with the symmetric 
difference area metric. To approximate a convex polygon, we find a simple 
fixed shape such as square, rectangle, or circle that minimizes the area 
of the symmetric difference with the polygon under homotheties. A 
homothety is a combined transformation with a translation and a scaling. 
Because of the scaling, our problem is very different from the problem 
using only translation.

In the future, we will design and analyze an algorithm to solve these 
problems. The result of the second problem is published in the journal 
Computational Geometry: Theory and Applications.


Date:			Friday, 3 October 2014

Time:                   11:00am - 1:00pm

Venue:                  Room 3501
                         lifts 25/26

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


**** ALL are Welcome ****