×

Congruence, similarity, and symmetries of geometric objects. (English) Zbl 0679.68070

Summary: We consider the problem of computing geometric transformations (rotation, translation, reflexion) that map a point set A exactly or approximately into a point set B. We derive efficient algorithms for various cases (Euclidean or maximum metric, translation or rotation, or general congruence).

MSC:

68Q25 Analysis of algorithms and problem complexity
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
20H15 Other geometric groups, including crystallographic groups
68W99 Algorithms in computer science
51F99 Metric geometry
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Aho, A. V., J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005
[2] Atallah, M. J., Checking Similarity of Planar Figures, Internat. J. Comput. Inform. Science13 (1984), pp. 279-290. · Zbl 0556.68047
[3] Atallah, M. J., On Symmetry Detection,IEEE Trans. Comput.34 (1985), pp. 663-666.
[4] Atkinson, M. D., An Optimal Algorithm for Geometrical Congruence,J. Algorithms8 (1987), pp. 159-172. · Zbl 0618.68041
[5] Collins, G.,Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition, Lecture Notes in Computer Science: Automata Theory and Formal Languages, Springer-Verlag, Berlin, 1975, pp. 134-183.
[6] Edelsbrunner, H.,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. · Zbl 0634.52001
[7] Highnam, P. T., Optimal Algorithms for Finding the Symmetries of a Planar Point Set,Inform. Process. Lett.22 (1986), pp. 219-222. · Zbl 0592.68064
[8] Mehlhorn, K.,Data Structures and Algorithms, Vols. 1, 2, 3, Springer-Verlag, Berlin, 1984.
[9] Martin, G. E.,Transformation Geometry, Springer-Verlag, New York, 1982. · Zbl 0484.51001
[10] Megiddo, N., Linear-Time Algorithm for Linear Programming in ℝ3 and Related Problems,SIAM J. Comput.12 (1983), pp. 759-776. · Zbl 0521.68034
[11] Mignotte, M., Identification of Algebraic Numbers,J. Algorithms3 (1982), pp. 197-204. · Zbl 0498.12004
[12] Preparata, F. P. and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985. · Zbl 0759.68037
[13] Schirra, St., Über die Bitkomplexität der ɛ-Kongruenz, Diplomarbeit, FB Informatik, Universität des Saarlandes, 1987.
[14] Wunderlich, W.,Ebene Kinematik, Bibliographisches Institut, Mannheim, 1970. · Zbl 0225.70002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.