CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:20120117-151248754

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120117-151248754

Abstract

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
http://dx.doi.org/10.1109/SFCS.1998.743439DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=743439&tag=1PublisherUNSPECIFIED
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:http://resolver.caltech.edu/CaltechAUTHORS:20120117-151248754
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=743439&isnumber=15971
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28821
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:17 Jan 2012 23:54
Last Modified:17 Jan 2012 23:54

Repository Staff Only: item control page