APPROXIMATION ALGORITHMS FOR POINT PATTERN MATCHING AND SEARCHI NG

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₁

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₁ metric with an expected distortion of O(log<super>2</super> n log D).