The problem of shape matching is ubiquitous in many domains as disparate as computational biology, computer vision, computational geometry and (multimedia) databases. The main challenges in this area have been to define notions of shape representation and shape similarity that are effectively computable as well as being relevant to the application at hand.
At its most basic, shape matching can be viewed as point matching; given two collections of points, each representing a certain shape, compute the similarity between them. In general, one can view the area of geometric matching as shape matching with geometric features (points, curves, surfaces and others).
The first part of this thesis presents algorithms for various problems in the domain of geometric matching. The unifying theme running through the algorithms is the use of approximations to obtain efficient algorithms. In addition, empirical results are presented that establish the practicality of the algorithms proposed therein.
The field of rational drug design has been greatly enhanced by the advent of computer-assisted techniques, most significantly in the area of molecular similarity search as applied in drug design, where the primary goal is to ``take a set of flexible and dissimilar active molecules, extract the features of similarity between them and use that information to design novel dissimilar molecules with biological activity''.
The second part of this thesis presents an extended case study of geometric matching in the context of molecular similarity search in the form of RAPID, a software system for performing molecular similarity search to aid in pharmacophore identification. The system was developed in collaboration with researchers at Pfizer Laboratories, and achieves significantly better performance than the systems currently in place.