Geometric matching problems

Abstract

모양매칭 문제는 컴퓨터 그래픽스, 컴퓨터 비전과 같은 분야에서 널리 쓰이는 문제이다. 주로 점이나 다각형과 같은 기하물체의 유사정도를 하우스돌프 거리(Hausdorff Distance)나 겹침넓이와 같은 기하함수를 이용하여 측정한다. 본 학위논문에서는 총 세 가지 모양매칭 문제를 다룬다.

첫 번째는 점집합 부분매칭 문제로 점의 개수가 각각 $n$과 $m$인 두 점집합이 주어졌을 때 병목거리(Bottleneck Distance)를 $\eps$ 이하로 가지는 평행이동을 찾는 문제이다. 병목거리는 항상 같은 개수의 두 점집합에서 정의되기 때문에 가장 큰 부분집합을 고려하여 계산한다. 본 학위논문에서는 2차원에서의 근사 문제를 다루었으며 $\eta$가 $\eps$에 대한 근사 변수일 때 $O(n^{2.5}m\log{\frac{n}{\eta}})$인 알고리즘을 제시한다.

두 번째로 두 3차원 볼록다면체가 주어졌을 때 겹침 부피를 최대로 하는 강체이동을 찾는 문제를 다룬다. 여기서 두 볼록다면체의 최대 겹침 부피가 항상 두 볼록다면체의 일정 비율 이상이라고 가정한다. 강체이동이란 평행이동과 회전이동을 말한다. 평행이동만을 허용했을 때 최대 겹침 부피를 계산하는 알고리즘이 이미 현존하기 때문에 이를 이용하여 회전이동을 적절히 추출하는 방법으로 최대 겹침 부피의 $(1-\eps)$배 이상인 강체이동을 찾아주는 알고리즘을 소개한다.

마지막으로 대칭차부피(Volume of the Symmetric Difference)를 유사도로 하는 볼록다면체 매칭문제를 다룬다. 이 문제에서는 볼록다면체의 평행이동과 확대축소만 허용한다. 대칭차부피 함수는 허용한 이동공간에서 두 개 이상의 국소최저값을 가질 수 있지만 제한된 정의역에서 유일한 최저값을 가진다는 것을 증명함으로 볼록 제한식 계획(Convex Programming)을 이용할 수 있다는 것을 보인다. 또한 대칭차부피 함수의 국소최적값을 가지는 이동들의 필요충분조건에 대하여 알아본다.