Optimal algorithms for symmetry detection in two and three dimensions (Q1822243)

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 \(\Theta\) (n) for polygons and \(\Theta\) (n log n) for two- and three-dimensional point sets. \(\Theta\) (n log n) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs \(\Theta\) (n) time can be achieved. All algorithms are optimal in time complexity, within constants.