Abstract
We address the question of determining if two point sets are congruent. This task consists of defining the concept of point congruence, and developing algorithms that test for it. We introduce the (ε,κ)-map, a device which pictorially represents the degree of congruence between two point sets. Point set congruence has been studied by previous researchers, but we feel that our definitions offer a more general and powerful approach to the problem. By using the paradigm of approximate algorithms, we are able to construct the (ε,κ)-map efficiently.
Supported in part by the U.S. Army Research Office, Grant No. DAAL03-92-G-0378
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl, “Congruence, similarity, and symmetries of geometric objects,” Discrete and Computational Geometry, 3 (1988), pp. 237–256.
E.M. Arkin, K. Kedem, J.S.B. Mitchell, J. Sprinzak, M. Werman, “Matching points into noise regions: combinatorial bounds and algorithms,” ORSA J. on Computing, 4 (1992), pp. 375–386.
H.S. Baird, Model-Based Image Matching Using Location, MIT Press, 1984.
T. Feder and R. Motwani, “Clique partitions, graph compression and speeding-up algorithms,” in Proc. of the 23rd ACM Symp. on Theory of Computing, 1991.
P.J. Heffernan and S. Schirra, “Approximate decision algorithms for point set congruence,” in Proc. of 8th ACM Symp. on Computational Geometry (1992), pp. 93–101; to appear in Computational Geometry: Theory and Applications.
G.E. Martin, Transformation Geometry, Springer Verlag, 1982.
K. Mehlhorn, Data Structures and Algorithms 2: Graph Algorithms and NP-completeness, Springer-Verlag, 1984.
F.P. Preparata and M.I. Shamos, Computational Geometry — An Introduction, Springer-Verlag, 1985.
S. Schirra, Über die Bitkomplexität der ε-Kongruenz, Diplomarbeit, Universität des Saarlandes, Saarbrücken, Germany, 1988.
S. Schirra, “Approximate decision algorithms for approximate congruence,” Information Processing Letters, 43 (1992), pp. 29–34.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heffernan, P.J. (1993). Generalized approximate algorithms for point set congruence. In: Dehne, F., Sack, JR., Santoro, N., Whitesides, S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57155-8_263
Download citation
DOI: https://doi.org/10.1007/3-540-57155-8_263
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57155-1
Online ISBN: 978-3-540-47918-5
eBook Packages: Springer Book Archive