Abstract
We propose a simple and efficient general algorithm for determining both rotational and involutional symmetries of polyhedra. It requiresO(m 2) time and usesO(m) space, wherem is the number of edges of the polyhedron. As this is the lower bound of the symmetry detection problem for the considered output form, our algorithm is optimal. We show that a slight modification of our symmetry detection algorithm can be used to solve the related conguity problem of polyhedra.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alt H, Mehlhorn K, Wagener H, Welzl E (1988) Congruence, similarity, and symmetries of geometric objects. Discrete Comput Geom 3:237–256
Ball WWR (1892) Mathematical recreations and problems. Macmillan, London
Berge C (1985) Graphs. North-Holland, Amsterdam
Bykat A (1979) On polygon similarity. In Process Lett 9:23–25
Eades P (1988) Symmetry finding algorithms. In: Toussaint, GT (ed) Computational morphology, North-Holland, pp 41–51
Eades P, Ng HC (1987) An algorithm for detecting symmetries in line drawings. Ars Combinatoria 23A:95–104
Hopcroft JE, Wong JK (1974) Linear time algorithm for isomorphism of planar graphs. Proceedings of 6th Annual ACM Symposion on Theory of Computing, pp 172–184
Jiang XY, Bunke H (1992) A simple and efficient algorithm for determining the symmetries of polyhedra. CVGIP: Graph Models Image Process 54:91–95
Jiang XY, Bunke H (1993) Detection and application of polyhedral symmetry: review. Proceedings of the 8th Scandinavian Conference on Image Analysis, Tromsø, Norway, pp 345–352
Jiang XY, Bunke H (1995) Exploration of object symmetries in computer vision and robotics. In: Bunke H, Kanade T, Noltemeier H, (eds) Modelling and Planning for Sensor Based Intelligent Robot Systems, World Scientific, pp 257–271
Lin JC, Chou SL, Tsai WH (1992) Detection of rotationally symmetric shape orientations by fold-invariant shape-specific points. Patt Recogn 25:473–482
Ore O (1962) Theory of graphs. Am Math Soc, Providence, RI, p 41
Preparata FR, Shamos MI (1985) Computational geometry. Springer Berlin Heidelberg, New York
Sugihara K (1984) Annlogn algorithm for detecting the congruity of polyhedra. J Comput Syst Sci 29:36–47
Waltzman R (1989) Geometric problem solving by machine visualization. Technical Report CS-TR-2291, University of Maryland, College Park, Md
Weinberg L (1996) A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Trans Circuit Theory 13:142–148
Wolter JD, Woo TC, Volz RA (1985) Optimal algorithms for symmetry detection in two and three dimensions. Vis Comput 1:37–48
Zabrodsky H, Peleg S, Arnir D (1992) A measure of symmetry based on shape similarity. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 703–706
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jiang, X., Yu, K. & Bunke, H. Detection of rotational and involutional symmetries and congruity of polyhedra. The Visual Computer 12, 193–201 (1996). https://doi.org/10.1007/BF01782322
Issue Date:
DOI: https://doi.org/10.1007/BF01782322