2
$\begingroup$

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.: If

polygonA = ( (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 terminology

Assume 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$.

Problem

In 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?

$\endgroup$
  • $\begingroup$ Do we have a way to hash elements of $X$, via some hash function? This is less than a comparison operator, but more than just being able to test two elements of $X$ for equality. $\endgroup$ – D.W. Apr 11 '14 at 5:18
  • $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Apr 11 '14 at 6:42
  • $\begingroup$ @Raphael: I thought that the question is very specific. "Does a linear algorithm exist that for a defined input provides a defined output?" Definitions are all stated in the description, again quite specific (unless I have to define what a set, sequence, natural numbers or modular arithmetic are). Could you please state where you see an ambiguity, i.e. what is to "specify"? $\endgroup$ – Zipper Apr 11 '14 at 10:02
  • $\begingroup$ @D.W. No hash function is available for $X$. Unfortunately the environment of the problem doesn't even provide data of a setoid. With some tweaks, the $X$ can be viewed as a setoid, although with the price that algorithms provide invalid results for certain inputs. I'm aware of that and I'm accepting such trade-off. $\endgroup$ – Zipper Apr 11 '14 at 10:12
  • $\begingroup$ Have you read my comment? ("unclear what you're asking" is just a close reason for lack of a better fitting one) $\endgroup$ – Raphael Apr 11 '14 at 10:15
1
$\begingroup$

It might depend on $n$. If $n$ is prime then the following algorithm works in linear time. Compare $a_1$ to all elements in $a$ and to all elements in $b$. The resulting $a_1$ patterns must be congruent, and if they are, then they are congruent uniquely. Once you know the shift, it is easy to check whether the original sequences are congruent.

When $n$ is composite then you might run into trouble since there are several shifts possible. Still, it seems possible but messy to get a linear or quasilinear time algorithm.

$\endgroup$
  • $\begingroup$ $n$ is an arbitrary natural number and sadly, in the actual data the $n$ is mostly an even number on top of it. :-/ $\endgroup$ – Zipper Apr 11 '14 at 10:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.