Real world background: There are 2 independent sources of polygon definitions, with arbitrary parameters. Meaning each source has it's own floating point precision, starting point and orientation of vertices.The problem is to find an algorithm, that would receive those 2 polygon definitions and by a certain margin declare them equal or not. If a cutting machine would receive those 2 inputs, would it cut out the same shapes? (Which is btw. the real motivation behind the problem.)E.g.: IfpolygonA = ( (1.0001, 1.0002), (2.0000, 1.0001), (1.5001, 1.9998) )polygonB = ( (1.9998, 0.9999), (0.9999, 1.0002), (1.5002, 2.0001) )and there is precision margin of 0.001 (i.e. 1 mm) then polygonA would be equal to polygonB.This problem can formally formulated as follows:Task and terminologyAssume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$.We define, that two sequences are congruent and denote them $S_1 \cong S_2$ if $\exists k,l \in [1..n]$ such that $a_{k+i \pmod{n}}=b_{l+i \pmod{n}}, \forall i \in [1..n]$. (Plainly said, they would define the same cycle.) If $S_1 \cong S_2$ then we say that $S_1$ is a rotation of $S_2$ and vice-versa.The task is to find an algorithm that determines if $S_1 \cong S_2$.ProblemIn the case that $X$ is a total order set the task can be solved quite easily with a linear algorithm. (Finding a lexicographical extremum of all rotations for both sequences and then comparing those extrema.)The question is, is there linear algorithm if $X$ is a setoid? I.e. members of $X$ can be checked only for equivalence. If not, does at least exist an algorithm with a better complexity than brute force?
How to check if two sequences of setoid members are mutual rotations?
algorithms;discrete mathematics