?

Log in

No account? Create an account
передний план - задний план - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

передний план - задний план [сент. 3, 2015|02:02 am]
Anatoly Vorobey
[Tags|]

Зачем спать, если можно всю ночь смотреть на эту картинку?

СсылкаОтветить

Comments:
[User Picture]From: cousin_it
2015-09-05 09:38 pm

Re: Завораживающее зрелище.

Мне кажется, это не очень интересный вопрос.

Давно известно, что для наборов из нескольких многоугольников такого алгоритма нет (Wang tiles). Глубокая причина в том, что любой частный случай проблемы остановки (остановится данная машина Тьюринга или нет) можно перекодировать в проблему замощения плоскости (придем ли мы к противоречию, если начнем мостить такими многоугольниками, или нет). Там и многоугольников особых не надо, достаточно квадратов с различными парами "ключ-замок" на каждой стороне. А уж про проблему остановки мы прекрасно знаем, почему она алгоритмически неразрешима.

На этом фоне исходный вопрос выглядит довольно скучно. Может быть, есть какой-то комбинаторный трюк, чтобы обойтись одним многоугольником вместо нескольких. А может быть, и нет. Вряд ли на этом пути найдется что-то глубокое и интересное.

Edited at 2015-09-05 21:39 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: gaz_v_pol
2015-09-08 11:17 am

Re: Завораживающее зрелище.

Володь, это вопрос философский. Лично мне это совсем не кажется скучным -- очень, очень интересно было бы выяснить, есть ли пример многоугольника, которым можно замостить всю плоскость, но любой из способов является непериодическим. В пространстве такой пример есть (Schmitt-Conway biprism). А на плоскости, несмотря на все старания, удается лишь пример набора из двух многоугольников привести. При этом победа кажется очень близкой, есть пример несвязного "многоугольника" с этим свойством (Socolar–Taylor tile). Но почему-то не получается.

Еще забавнее ситуация с замощением выпуклыми многоугольниками. Минимальный пример содержит 3 многоугольника, и свести их до двух почему-то не выходит. Я над этим думал так и эдак -- загадка природы какая-то.

И чтоб два раза не вставать. Если отказаться от требования непериодичности, и рассматривать замощения трехмерного пространства копиями какого-то выпуклого многогранника -- спрашивается, сколь много может быть у него граней? Для аналогичной плоской задачи ответ известен -- плоскость нельзя разбить на равные выпуклые 7-угольники (или n-угольники при n>6). А для пространства нет не только верхней оценки, но даже и не доказано, что она вообще существует. Т.е. наука не знает, можно ли пространство разбить на равные выпуклые миллион-гранники. По-моему, здорово.
(Ответить) (Parent) (Thread)