APPROXIMATION ALGORITHMS FOR POINT PATTERN MATCHING AND SEARCHI NG
APPROXIMATION ALGORITHMS FOR POINT PATTERN MATCHING AND SEARCHI NG
Files
Publication or External Link
Date
2010
Authors
Cho, Minkyoung
Advisor
Mount, David M
Citation
DRUM DOI
Abstract
Point pattern matching is a fundamental problem in computational geometry.
For given a reference set and pattern set, the problem is to find a
geometric transformation applied to the pattern set that minimizes some
given distance measure with respect to the reference set. This problem has
been heavily researched under various distance measures and error models.
Point set similarity searching is variation of this problem in which a
large database of point sets is given, and the task is to preprocess
this database into a data structure so that, given a query point set,
it is possible to rapidly find the nearest point set among elements of
the database. Here, the term <italic>nearest</italic> is understood in
above sense of pattern matching, where the elements of the database may be
transformed to match the given query set. The approach presented here is
to compute a low distortion embedding of the pattern matching problem into
an (ideally) low dimensional metric space and then apply any standard
algorithm for nearest neighbor searching over this metric space.
This main focus of this dissertation is on two problems
in the area of point pattern matching and searching algorithms:
(i) improving the accuracy of alignment-based point pattern matching and
(ii) computing low-distortion embeddings of point sets into vector spaces.
For the first problem, new methods are presented for matching point sets
based on alignments of small subsets of points. It is shown that these methods
lead to better approximation bounds for alignment-based planar point pattern
matching algorithms under the Hausdorff distance. Furthermore, it is shown
that these approximation bounds are nearly the best achievable by alignment-based
methods.
For the second problem, results are presented for two different distance
measures. First, point pattern similarity search under translation for point sets
in multidimensional integer space is considered, where the distance function is
the symmetric difference. A randomized embedding into real space under the L<sub>1</sub>
metric is given. The algorithm achieves an expected distortion of O(log<super>2</super> n).
Second, an algorithm is given for embedding R<super>d</super> under the Earth Mover's
Distance (EMD) into multidimensional integer space under the symmetric difference
distance. This embedding achieves a distortion of O(log D), where D is
the diameter of the point set. Combining this with the above result implies that
point pattern similarity search with translation under the EMD can be embedded in
to
real space in the L<sub>1</sub> metric with an expected distortion of O(log<super>2</super> n log D).