Checking similarity of planar figures
DOI: 10.1007/BF00977833
关键词: Theory of computation 、 Search problem 、 Computational geometry 、 Computer science 、 Similarity (geometry) 、 Ellipse 、 Similitude 、 Combinatorics 、 Analysis of algorithms 、 Pattern recognition (psychology) 、 Theoretical computer science 、 Computational Theory and Mathematics
摘要: Two planar figures aresimilar if a scaled version of one them can be moved so that it coincides with the second figure. The problem checking whether two are similar is relevant to both computational geometry and pattern recognition. An efficient algorithm known for polygonsP andQ similar(1) purpose this note give an figuresP when no longer constrained polygons. We anO(n logn) time solving each figure consists collection (possibly intersecting) straight line segments, circles, ellipses. Our easily modified which include other geometric patterns as well. also prove our optimal.
springer.com
sci-hub.se 参考文章(4)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Glenn Manacher, An application of pattern matching to a problem in geometrical complexity Information Processing Letters. ,vol. 5, pp. 6- 7 ,(1976) , 10.1016/0020-0190(76)90092-2
Edward M. Reingold, On the Optimality of Some Set Algorithms Journal of the ACM. ,vol. 19, pp. 649- 659 ,(1972) , 10.1145/321724.321730
I. M. Yaglom, Allen Shields, Geometric Transformations I ,(1962)