A Caltech Library Service

Pattern Matching for Spatial Point Sets

Cardoze, David E. and Schulman, Leonard J. (1998) Pattern Matching for Spatial Point Sets. In: 39th Annual Symposium on Foundations of Computer Science: Proceedings. IEEE Computer Society , Los Alamitos, CA, pp. 156-165. ISBN 0-8186-9172-7.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Two sets of points in d-dimensional space are given: a data set D consisting of N points, and a pattern set or probe P consisting of k points. We address the problem of determining whether there is a transformation, among a specified group of transformations of the space, carrying P into or near (meaning at a small directed Hausdorff distance of) D. The groups we consider are translations and rigid motions. Runtimes of approximately O(nlogn) and O(n^dlogn) respectively are obtained (letting n=max{N,k} and omitting the effects of several secondary parameters). For translations, a runtime of approximately O(n(ak+1)log^2n) is obtained for the case that a constant fraction α<1 of the points of the probe is allowed to fail to match.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 1998 IEEE. Date of Current Version: 06 August 2002. Thanks to Amihood Amir and Piotr Indyk for helpful communications.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6128780
Record Number:CaltechAUTHORS:20120117-151248754
Persistent URL:
Official Citation:Cardoze, D.E.; Schulman, L.J.; , "Pattern matching for spatial point sets," Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on , vol., no., pp.156-165, 8-11 Nov 1998 doi: 10.1109/SFCS.1998.743439 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28821
Deposited By: Ruth Sustaita
Deposited On:17 Jan 2012 23:54
Last Modified:09 Nov 2021 17:01

Repository Staff Only: item control page