Поиск базовой ячейки мозаики, P или NP?

[Enfernuz]

Всем привет.
Имеется мозаика (набор многоугольников нескольких типов, плотно замощающих плоскость). Нужно найти такой набор многоугольников (т.н. базовую ячейку), трансляция которого позволит замостить плоскость (т.е. трансляция которого даст нам исходную мозаику).
Мне кажется, поиск такой ячейки --- задача из класса NP. Доказать это у меня, к сожалению, опыта не хватает, но уж очень эта задача походит на Square-Tiling problem, а она NP-полная.
Заранее спасибо за любую помощь в данном вопросе.

[Sonic86]

Я правильно понял?: даны ячейки $K_1,\ldots,K_n$ и достаточно найти многоугольник $K$, из экземпляров которого можно собрать каждый многоугольник $K_j$ (и тогда вся плоскость будет покрыта $K$)? Если да, то просто $K$ может и не существовать. Например, пусть $n=2$, $K_1$ - прямоугольник со сторонами $1,10$, $K_2$ - прямоугольник со сторонами $10,\sqrt{2}$. Составляем только из $K_1$ слои вида $a\leqslant x \leqslant a+1, y\in\mathbb{R}$, а только из $K_2$ слои вида $a\leqslant x \leqslant a+\sqrt{2}, y\in\mathbb{R}$ - эти слои замощают плоскость - задача сводится к одномерному случаю: замостить отрезками длиной $1$ или $\sqrt{2}$ всю прямую. Но в одномерном случае, очевидно, $K=\text{НОД}(K_1,K_2)$, но вот именно в таком случае $K$ не существует (а если существует, то находится за логарифмическое время).

В общем, боюсь, что я чего-то не понял

[Enfernuz]

Спасибо за отклик!
Во избежание недопониманий, вот несколько картинок. Базовые ячейки (или, если хотите, базовые домены) обозначены чёрными линиями.




Извиняюсь за неточное описание проблемы. Вообще, моя задача усложняется тем, что в мозаике многоугольники могут иметь разные цвета. Известно, что из такими многоугольниками (например, на первой картинке: красные шестиугольники и зелёные треугольники) можно замостить плоскость. Необходимо найти такой набор многоугольников, который включал бы в себя многоугольники каждого цвета, и которым можно замостить плоскость.

[ИСН]

Вы что в точности называете мозаикой? Что дано? Если набор многоугольников, то тут может существовать куча разных замощений с разными составами многоугольников. А также и с одинаковыми.

[Enfernuz]

Имеется конкретное замощение плоскости многоугольниками определенных цветов. Необходимо в нём выделить минимальный набор многоугольников каждого цвета, трансляция которого даст исходное замощение. В таком наборе в общем случае может быть как один многоугольник своего цвета, так и несколько.

[Sonic86]

Enfernuz в сообщении #577557 писал(а):

Имеется конкретное замощение плоскости многоугольниками определенных цветов. Необходимо в нём выделить минимальный набор многоугольников каждого цвета, трансляция которого даст исходное замощение. В таком наборе в общем случае может быть как один многоугольник своего цвета, так и несколько.

Минимальный набор не обязан существовать. Да и что такое "трансляция"? - произвольный параллельный перенос?
Вы представляете насколько сложны могут быть мозаики? Вот, например, пример непериодического замощения - мозаика Пенроуза.
В ней нет минимального набора и вряд ли есть общая ячейка.

[ИСН]

А, тогда просто: находим элементарную ячейку (если она там вообще есть, т.е. если это не узор пенроуза) и приписываем к ней все многоугольники, у которых, например, центр тяжести находится в ней.

[Enfernuz]

Sonic86 в сообщении #577565 писал(а):

Минимальный набор не обязан существовать. Да и что такое "трансляция"? - произвольный параллельный перенос?
Вы представляете насколько сложны могут быть мозаики? Вот, например, пример непериодического замощения - мозаика Пенроуза.
В ней нет минимального набора и вряд ли есть общая ячейка.

Я и не утверждаю, что он существует. Как бы это цинично не звучало, но мне бы даже удобнее было бы, если бы он не всегда существовал :)

ИСН в сообщении #577568 писал(а):

А, тогда просто: находим элементарную ячейку (если она там вообще есть, т.е. если это не узор пенроуза) и приписываем к ней все многоугольники, у которых, например, центр тяжести находится в ней.

Для произвольной периодической мозаики существует ли полиномиальный алгоритм нахождения элементарной ячейки?

P.S. Прошу прощения за такие наивные вопросы --- начал заниматься этой темой совсем недавно.

[ИСН]

В какой форме у Вас задана произвольная периодичная мозаика? А то я, например, привык к такой форме, в которой сначала указана элементарная ячейка, потом координаты объектов в ней - но это, очевидно, не Ваш случай.

[Enfernuz]

ИСН в сообщении #577585 писал(а):

В какой форме у Вас задана произвольная периодичная мозаика? А то я, например, привык к такой форме, в которой сначала указана элементарная ячейка, потом координаты объектов в ней - но это, очевидно, не Ваш случай.

По-честному, всё довольно первобытно: мозаика в программе задана конечным набором раскрашенных фигур и их координатами. Допускается, что она периодическая (установлено наблюдателем :) ). Исходя из этой информации необходимо выделить элементарную ячейку.

[ИСН]

Если перенести сюда кристаллографический подход, то примерно так. Взять одну фигуру. Выделить все фигуры такого же типа. Выписать все вектора между ними. Отсортировать по длине. (тут выброшено...) Начиная с самых коротких, проверять на совмещение картинки при сдвиге на такой вектор. Как только найдено два хороших неколлинеарных вектора - это ячейка. Привести к стандартному виду. Ну и если нас не интересует симметрия, то в общем-то всё.

[Enfernuz]

Спасибо за советы. Буду думать :)