ISSN:
1432-2315
Keywords:
Symmetry
;
Similarity
;
Computational geometry
;
Pattern matching
;
Graph isomorphism
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01901268
Permalink