Polygon recognition and symmetry detection (Q1405723)

The paper contains an approach to recognition and symmetry detection of polygons or parts of them in various geometries. Let \(M\) be a manifold on which a Lie group \(G\) is acting. Then to any polygon \((p_1, \dots, p_k)\) on \(M\) an ordered set of invariants \(I_1, \dots, I_n\), called a signature, can be attached which uniquely determines the polygon up to transformations of \(G\). This means that two polygons \((p_1, \dots, p_k)\) and \((q_1, \dots, q_k)\) have the same signature if and only if there is a transformation \(g \in G\) with \(g(p_i) = q_i\). The author shows how to construct such signatures for a general Lie group \(G\) and discusses in detail examples for the cases where \(G\) is the special Euclidean, the Euclidean, the similarity, the affine or the equiaffine group acting in the plane or the group \(SL(2)\) acting in the Poincaré halfplane. The signatures also facilitate the detection of symmetries or partial equivalences of two polygons. The time complexity of the algorithms is linear in the number \(k\) of vertices and moreover these algorithms are noise resistant and hence can also be used to decide whether two polygons are 'roughly' equivalent.