Комбинации поворотов и отражений

[denny]

Сейчас разбираюсь с паттернами по типу centroidal Voronoi tesselations (или K-Means clustering).
В данном случае рассмотрим квадрат $(-1,1)\times(-1,1)$. Например, получены такие множества центров кластеризации:



Нам важна структура паттерна, поэтому случаи 1 и 4, например, считаются одинаковыми, а 2 и 3 - нет.
Более точно:
Паттерны считаются одинаковыми, если они совмещаются (хотя бы одним из):

- Поворотами на $\pm\pi/2,\pm\pi$

- Отражениями относительно осей $X$, $Y$, главных диагоналей и центра координат

- Любой композицией данных операций

И вот тут я запутался. Ясно, что многие комбинации (и сами операции) эквивалентны.
Например, отражение относительно центра эквивалентно повороту на $\pm\pi$.
Разобрался также в этой статье.
Догадываюсь, что не нужно рассматривать бесконечное число композиций.
Но какое минимальное число операций достаточно рассмотреть, чтобы убедиться, в том что паттерны совмещаются или нет в указанном смысле?

ЗЫ. Стоит уточнить, что паттерны, конечно, получаются с определенной точностью, поэтому факт совмещения оценивается как некая минимальная ошибка. Этот вопрос я решил. Другое дело, что очень желательно включить в число операций тавтологию, или поворот на нулевой угол.

[dgwuqtj]

Речь идёт про действие группы $\mathrm D_4$ (диэдральная группа). В ней 8 элементов: тождественное преобразование, центральная симметрия, 4 отражения (относительно вертикальной оси, горизонтальной оси и обеих диагоналей), ну и 2 поворота на $\frac \pi 2$ в разные стороны. Так как это группа, то она замкнута относительно композиции.

[denny]

Да, спасибо, что-то такое предполагал!

[svv]

Прочитать про эту группу можно здесь (она там ещё обозначается $\mathrm{Dih}_4$).
Все её элементы можно получить произведением (композицией) двух образующих. По ссылке это
$a$ — поворот на 90° по часовой стрелке;
$b$ — отражение относительно оси $Oy$.
Выбор образующих неоднозначен, например, ничем не хуже было бы в качестве $a$ взять поворот против часовой на 90°.

[denny]

svv в сообщении #1614767 писал(а):

Прочитать про эту группу можно здесь (она там ещё обозначается $\mathrm{Dih}_4$).
Все её элементы можно получить произведением (композицией) двух образующих. По ссылке это
$a$ — поворот на 90° по часовой стрелке;
$b$ — отражение относительно оси $Oy$.
Выбор образующих неоднозначен, например, ничем не хуже было бы в качестве $a$ взять поворот против часовой на 90°.

С буквой $F$ шикарный пример. Долго мучался, чтобы найти такой

Но все же, эквивалентность относительно только $a$ и $b$ недостаточно рассмотреть?
Как минимум 8 вариантов надо проверить, просто их можно получить как композиции?

[dgwuqtj]

Конечно, в том же примере с буквой F как раз для каждой картинки существует ровно одно преобразование, переводящее её в исходную.

[svv]

denny
В начале пункта есть две картинки с буквами F — чёрно-белая и цветная. К сожалению, в них используются разные соглашения о порядке записи композиции преобразований. В цветной картинке использован стандартный порядок справа налево (т.е. преобразование $ba=b\circ a$ эквивалентно выполнению сначала $a$, затем $b$). В чёрно-белой — нестандартный слева направо. И это несмотря на пояснение в том же пункте:

Цитата:

Given two such movements $x$ and $y$, it is possible to define the composition $x\circ y$ as above: first the movement $y$ is performed, followed by the movement $x$.

Будьте осторожны.
Кстати, проверка моих слов была бы хорошим упражнением.

[Doctor Boom]

Я обычно на это смотрю как на невырожденную перестановку единичных ортов, легко обобщается на любую размерность