Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/70591
Type: Artigo de periódico
Title: POINT SET PATTERN-MATCHING IN D-DIMENSIONS
Author: DEREZENDE, PJ
LEE, DT
Abstract: In this paper we apply computational geometry techniques to obtain an efficient algorithm for the following point set pattern matching problem. Given a set S of n points and a set P of k points in the d-dimensional Euclidean space, determine whether P matches any k-subset of S, where a match can be any similarity, i.e., the set P is allowed to undergo translation, rotation, reflection, and global scaling. Motivated by the need to traverse the sets in an orderly fashion to shun exponential complexity, we circumvent the lack of a total order for points in high-dimensional spaces by using an extension of one-dimensional sorting to higher dimensions (which we call ''circular sorting''). This mechanism enables us to achieve the orderly traversal we sought. An optimal algorithm (in time and space) is described for performing circular sorting in arbitrary dimensions. The time complexity of the resulting algorithm for point set pattern matching is O(n log n + kn) for dimension one and O(kn(d)) for dimension d greater than or equal to 2.
Subject: PATTERN MATCHING
CIRCULAR SORTING
SUBSET SIMILARITY
Editor: Springer Verlag
Rights: fechado
Date Issue: 1995
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOSA1995QK30600005.pdf923.43 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.