Optimal algorithms for symmetry detection in two and three dimensions |
| |
| Authors: | Jan D Wolter Tony C Woo Richard A Volz |
| |
| Affiliation: | (1) Department of Electrical Engineering and Computer Science, The University of Michigan, 48109 Ann Arbor, MI, USA;(2) Department of Industrial and Operations Engineering, The University of Michigan, 48109 Ann Arbor, MI, USA |
| |
| Abstract: | Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be  (n) for polygons and (n logn) for two- and three-dimensional point sets. (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs (n) time can be achieved. All algorithms are optimal in time complexity, within constants. |
| |
| Keywords: | Symmetry Similarity Computational geometry Pattern matching Graph isomorphism |
| 本文献已被 SpringerLink 等数据库收录！ |
|
