Abstract
The geometric shape matching problem reads as follows: given two shapes P and Q from a set of valid shapes
Π and a distance measure δ for these shapes, find a transformation τ from a set of valid
transformations T, such that the distance δ(τ(P),Q) is as small as possible. In this thesis we present
efficient algorithms for variants of this problem; the results can be grouped according to the shapes considered:
Point patterns in Rd: In the first part we consider point patterns; the shapes are point sets consisting of m and n
points in Rd, respectively.
Congruence test: We present an algorithm to decide in O(n ⌈d/3 ⌉ log n) time (m < n), whether there is a
congruence, that maps P onto Q (this can be considered as a special case of the shape matching problem where the
distance measure is the discrete metric).
Hausdorff-distance: We give the first non-trivial algorithm to compute the directed Hausdorff-distance h(P,Q) from a
set of points P to a set Q of semialgebraic sets of constant description complexity each (this can be considered as a
special case of the shape matching problem where the identity is the only valid transformation); the runtime is
Oε(m nε log m+m1+ε-1/(2d-2) n).
Planar curves: The second part deals with the shape matching problem for polygonal curves in the plane; the shapes
are polygonal chains P,Q with m and n vertices, respectively. The distance measure is the Frechét-distance F(P,Q)
of P and Q.
Matching under translations: We give the first algorithm for matching polygonal chains with respect to the
Frechét-distance under translations; the runtime is O((m n)3(m+ n)2). Furthermore we describe an O(ε-2 m
n) approximation algorithm of quality (1+ε) by generalizing reference-point based methods. Finally we prove
that reference-points for affine maps do not exist.
Hausdorff- vs. Frechét-distance: We show that the Frechét- and the Hausdorff-distance are linearly related for a
certain class of curves. For curves of that type we describe an O((m+ n) log2(m+ n) 2α(m+ n)) time
approximation algorithm to compute F(P,Q). We conclude with the first non-trivial algorithm to detect such curves; it
runs in O(n log2 n) time.
Simple polyhedral surfaces in R3: In the last part we consider shapes that are composed of sets P and Q of m and
n disjoint triangles in R3.
Hausdorff-distance: We develop an algorithm that computes H(P,Q), the Hausdorff-distance between P and Q, in
Oε((m n)15/16+ε (m17/16+ n17/16)) time. |
