Object recognition algorithms are fundamental tools in automatic matching of geometric shapes within a background scene. Many approaches have been proposed in the past to solve the object recognition problem. Two of the key aspects that distinguish them in terms of their practical usability are: (i) the type of input model description and (ii) the comparison criteria used. In this paper we introduce a novel scheme for 3D object recognition based on line segment representation of the input shapes and comparison using the Hausdor distance. This choice of model representation provides the flexibility to apply the scheme in different application areas. We define several variants of the Hausdor distance to compare the models within the framework of well defined metric spaces. We present a matching algorithm that efficiently finds a pattern in a 3D scene. The algorithm approximates a minimization procedure of the Hausdor distance. The output error due to the approximation is guaranteed to be within a known constant bound. Practical results are presented for two classes of objects: (i) polyhedral shapes extracted from segmented range images and (ii) secondary structures of large molecules. In both cases the use of our approximate algorithm allows to match correctly the pattern …