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. https://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: https://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: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 1998 IEEE. Date of Current Version: 06 August 2002. Thanks to Amihood Amir and Piotr Indyk for helpful communications. | |||||||||
| Other Numbering System: |
| |||||||||
| DOI: | 10.1109/SFCS.1998.743439 | |||||||||
| Record Number: | CaltechAUTHORS:20120117-151248754 | |||||||||
| Persistent URL: | https://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: | 09 Nov 2021 17:01 |
Repository Staff Only: item control page
