Невыпуклый многоугольник

[staric]

Середины соседних сторон невыпуклого n-угольника соединяют отрезками, получая ломанную. Если она ограничивает невыпуклый n-угольник, процедуру повторяем, если получается самопересекающаяся ломанная или выпуклый n-угольник, прекращаем. При каком минимальном n возможно:
а) проделать 2020 шагов?
б) продолжать процедуру бесконечно?

[waxtep]

Шестиугольник в виде "зайца с ушами" выглядит перспективно, после первой операции он превращается в "шеврон", а потом опять в "зайца" (но с ушками покороче). То есть, исходная фигура - квадрат, у которого вместо двух противоположных сторон приделаны острые углы, так, что если соединить их вершины, получится линия, параллельная оставшимся двум сторонам квадрата

[waxtep]

Хммм, видимо, рецепт зайца годится только для п. (а); в самом деле, возьмем шестиугольник

$$ABCDEF,A(-2,b+1),B(-1,-1),C(1,-1),D(2,b+1),E(1,1),F(-1,1),b>0$$

После двух итераций он превратится в аналогичного "зайца", но, не подобного геометрически, высота "ушек" станет в три раза меньше (если сдвинуть начало координат и изменить масштабы в полтора $4/3$ раза, придем к тому же $ABCDEF$, но с ординатами точек $A,D$ всего лишь $\frac{b+1}3$, вместо исходного $b+1$). Так что если взять $b>3^{1010}-1$, $2020$ итераций обеспечить можно, но вот бесконечно так баловаться не получится, "ушки поджимаются быстрее головы"

[slavav]

Перебор пятиугольников показывает что все они становятся выпуклыми за два шага максимум.

[waxtep]

Для п. (б) подходящим кажется 12-угольник, похожий на шильдик Митсубиши: равносторонний треугольник, в каждой стороне к-рого организовано по "впуклости" в виде угла вершиной внутрь. Не пытался пока проверить точно, но, кажется, что "впуклости" должны сохраняться всегда

[arseniiv]

waxtep
Скорее всего не сработает, потому что при определённых параметрах фигуры я смог на четвёртой итерации (сиреневая) получить явную выпуклость (что помогает увидеть штриховая серая линия):

-- Пн фев 10, 2020 00:29:45 --

Каждая операция «усреднения» сопоставляет вершине $A_i$ $n$-угольника (при обходе в фиксированном порядке) вершину $\frac12(A_i + A_{i+1})$ нового, где сложение в индексах понимается по модулю $n$. Тогда чем больше мы проделаем усреднений, тем ближе становится распределение весов $a_i$ в разложении $A^\text{новое}_1 = a_1A_1 + \ldots + a_nA_n$ к равномерному. Если правильно описать, что значит «ближе» (а само это распределение можно найти и явно — это wrapped (до $1..n$) биномиальное распределение с $p=\frac12$ и числом испытаний, равным количеству «усреднений»), то можно будет наверно отсечь класс фигур, которые из-за этого сглаживания весов станут выпуклыми, если не вообще все фигуры.

[waxtep]

arseniiv в сообщении #1439075 писал(а):

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

С другой стороны, простые правильные фигуры (равносторонний треугольник, квадрат) эта операция не сглаживает, а только сжимает и вращает. Может быть, для невыпуклого многоугольника попробовать "полоску, свернутую в спираль"? Она будет вращаться, сжиматься (и деформироваться), но, ведь, кажется, не сможет "распрямиться", если сделан полный оборот?

[arseniiv]

Что-то на основе манипуляций, которые я вручную проделал с фигурой выше, мне кажется, что спираль будет съедаться с концов. Надо бы какую-нибудь простую штуку для проверки и визуализации написать будет…

[slavav]

Подозреваю, что в пределе фигура сходится к правильному многоугольнику, если нормировать размер.

-- 10.02.2020, 09:51 --

Можно рассмотреть одномерную задачу. Если все точки спроектировать на любую прямую, то получим такую же задачу для чисел.
Задаётся функция $f_1: [0, N-1] \to \mathbb{R}$. Правило преобразования: $f_{i+1}(x) = \frac{f_i(x) + f_i(x + 1)}2$, Все индексы по модулю $N$. При каких $f_1$ последовательность сходится к синусу (отмасштабированному и смещённому по фазе)?
Оператор линейный, неужели такую задачу ещё не решили?

-- 10.02.2020, 10:00 --

Нам просто нужны собственные числа и вектора матрицы такого вида:

$$\begin{bmatrix} \frac12 & \frac12 & 0 & 0 & 0 \\ 0 & \frac12 & \frac12 & 0 & 0 \\ 0 & 0 & \frac12 & \frac12 & 0 \\ 0 & 0 & 0 & \frac12 & \frac12 \\ \frac12 & 0 & 0 & 0 & \frac12 \\ \end{bmatrix}$$

И какая-нибудь теорема что все итерации сходятся к набору собственных векторов. А вектора будут гармониками. Так?

-- 10.02.2020, 10:07 --

Двумерная задача тоже приводится к матричному виду, если игнорировать самопересечения. А их можно игнорировать если ответ на второй пункт отрицательный.

[waxtep]

arseniiv в сообщении #1439109 писал(а):

Что-то на основе манипуляций, которые я вручную проделал с фигурой выше, мне кажется, что спираль будет съедаться с концов. Надо бы какую-нибудь простую штуку для проверки и визуализации написать будет…

Сделал в экселе (просто в клетках, без попыток программировать), - эта зараза (спираль) еще и самопересекаться начинает

[waxtep]

Такая очень стилизованная (квадратная) буква "С" выглядит рабочей. Это тоже 12-угольник, грубо говоря, квадрат с интрузией внутрь, расширяющейся на конце. Я по крайней мере устал в экселе ее итерировать, пару десятков итераций она выдерживает (утоньшаясь и разгибаясь, но, сохраняя общую С-образную форму). Координаты и/или рисунок попозже размещу

[Утундрий]

Можно взять произвольный выпуклый $(n-2)$-угольник с одной маленькой (по сравнению с остальными) стороной и вдавить в него из середины этой стороны узкий "шип".

-- Пн фев 10, 2020 12:47:48 --

То есть, нечто вроде этого:

$$\begin{tikzpicture}\draw [blue, thick] (0,0) -- (5,.3) -- (5,.4) -- (-.2,.1) -- (-.2,-.1) -- (5,-.4) -- (5,-.3) -- (0,0);\end{tikzpicture}$$

[waxtep]

Утундрий, у такой $\Lambda$-ки нижняя (у Вас правая) часть очень быстро выполаживается

-- 10.02.2020, 12:58 --

А я вот такое имел в виду:

$$\begin{tikzpicture}\draw [black, thick] (2,-1) -- (5,-1) -- (5,-5) -- (-5,-5) -- (-5,5) -- (5,5) -- (5,1) -- (2,1) -- (2,2) -- (-2,2) -- (-2,-2) -- (2,-2) -- (2,-1);\end{tikzpicture}$$

После $10$ итераций (координаты округлены до $2$ знаков):

$$\begin{tikzpicture}\draw [black, thick] (1.22,1.87) -- (2.04,2.09) -- (1.95,1.74) -- (1.12,1.16) -- (0.38,0.41) -- (0.38,-0.41) -- (1.12,-1.16) -- (1.95,-1.74) -- (2.04,-2.09) -- (1.26,-1.87) -- (0.29,-0.77) -- (0.29,0.77) -- (1.22,1.87);\end{tikzpicture}$$

[waxtep]

Утундрий в сообщении #1439143 писал(а):

То есть, нечто вроде этого:

$$\begin{tikzpicture}\draw [blue, thick] (0,0) -- (5,.3) -- (5,.4) -- (-.2,.1) -- (-.2,-.1) -- (5,-.4) -- (5,-.3) -- (0,0);\end{tikzpicture}$$

да, конкретно эта "овыпукляется" на пятой итерации, вот такая будет:

$$\begin{tikzpicture}\draw [blue, thick] (2.41,0.18) -- (1.75,0) -- (2.41,-.18) -- (3.24,-.22) -- (3.28,-.1) -- (3.28,.1) -- (3.24,.22) -- (2.41,0.18);\end{tikzpicture}$$

[slavav]

Посчитал 50 итераций для буквы "C". Сходится. Надо доказывать.

-- 10.02.2020, 18:00 --

Про матричный подход: там все собственные числа равны. Предельные кривые могут быть очень разнообразны.