2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Невыпуклый многоугольник
Сообщение13.02.2020, 22:03 
Аватара пользователя


07/01/16
878
Аязьма
slavav в сообщении #1439749 писал(а):
Восьмиугольник удобно записать в радикалах:
$(8, \sqrt 2 + (8\sqrt 2 - 2)i, -10 + 16i, -\sqrt 2 + (8\sqrt 2 + 2)i, 12, -\sqrt 2 - (8\sqrt 2 + 2)i, -10 - 16i, \sqrt 2 - (8\sqrt 2 - 2)i)$
ух ты, даже 8-угольник! И, раз там только целые и корни из двух, любую его итерацию же можно выписать в явном виде, по крайней мере в принципе. Красота! :-)

 Профиль  
                  
 
 Re: Невыпуклый многоугольник
Сообщение15.02.2020, 09:57 


02/09/10
59
Гм. Пока полностью согласен только с ответом на п. а).
По б). Действительно, нетрудно проверить домножением указанного slavav вектора для восьмиугольника на матрицу :-)
$$\begin{bmatrix}
 1 & \frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4}\\
\frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4} & \frac12 \\
\frac12 & \frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4}\\
 \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} & 0 \\
 0 & \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} \\
\frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} & \frac12 \\
\frac12 & \frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4} & 1 & \frac {2+\sqrt{2}}{4} \\
\frac {2+\sqrt{2}}{4} & \frac12 & \frac {2-\sqrt{2}}{4} & 0 & \frac {2-\sqrt{2}}{4} & \frac12 & \frac {2+\sqrt{2}}{4} & 1 \\
\end{bmatrix}$$
,что представленный восьмиугольник вытягивается в пределе итераций в вертикальную струнку, однако остается пара вопросов:
- не потеряет ли он невыпуклость "по дороге"?
- как насчет n=6 и n=7?
Хотя в целом красиво сработано, что да - то да.

 Профиль  
                  
 
 Re: Невыпуклый многоугольник
Сообщение16.02.2020, 12:13 
Заслуженный участник


26/05/14
771
Первая геометрическая лемма
Образ круга - эллипс:
Рассмотрим $M: \mathbb{C} \to \mathbb{C}, M(x) = ax + b\overline{x}$, где $\overline{x}$ - операция сопряжения.
Можно доказать что образ единичной окружности $M({\left\lvert x\right\rvert = 1})$ есть эллипс с полуосями $\left\lvert a \right\rvert + \left\lvert b \right\rvert$ и $\left\lvert \left\lvert a \right\rvert - \left\lvert b \right\rvert \right\rvert$.
Если $\left\lvert a \right\rvert = \left\lvert b \right\rvert$, то эллипс вырождается в отрезок длины $4\left\lvert a \right\rvert$.

Вторая геометрическая лемма
Малые возмущения не портят выпуклость:
Дан выпуклый многоугольник $u$. $w_m$ последовательность ломаных (возможно самопересекающихся).
Можно доказать что если $\lim\limits_{m \to \infty}w_m = 0$, то найдётся $m_0$ такое что $u + w_{m_0}$ - выпуклый.

Обозначения
Первообразный корень из единицы порядка $n$: $\varepsilon_n = e^{\frac{2\pi i}{n}}$.
Отображение многоугольников задаёт оператор $A$ с собственными векторами и значениями:
$v_k=(1,\varepsilon_n^k, \varepsilon_n^{2k}, \dots, \varepsilon_n^{(n-2)k}, \varepsilon_n^{(n-1)k}), k = 0 \dots n-1$,
$\lambda_k=\frac{1 + \varepsilon_n^k}2, k = 0 \dots n-1$.

Пары собственных чисел и векторов сопряжены: $\lambda_k = \overline{\lambda_{n-k}}, v_k = \overline{v_{n-k}}, k = 1 \dots n - 1$.

Модули собственных чисел убывают к середине: $\left\lvert \lambda_k \right\rvert > \left\lvert \lambda_{k+1} \right\rvert, k = 0, \dots, \left\lfloor\frac{n-1}{2}\right\rfloor$.

Произвольный многоугольник в базисе из собственных векторов: $\sum\limits_{k=0}^{n-1} a_k v_k$.

Отобразим его $m$ раз: $A^m(\sum\limits_{k=0}^{n-1} a_k v_k) = \sum\limits_{k=0}^{n-1} a_k \lambda_k^m v_k$.

"Предел" итераций по $m$

Положим $a_0 = 0$. Он отвечает только за трансляцию всего многоугольника и не влияет на выпуклость так как $v_0 = (1, \dots, 1)$.
Положим $\left\lvert a_1 \right\rvert \ne \left\lvert a_{n - 1} \right\rvert$.

Все вершины многоугольника можно умножать или делить на один и тот же коэффициент. На выпуклость не влияет:
$\frac{A^m(\sum\limits_{k=1}^{n - 1} a_k v_k)}{\left\lvert\lambda_1^m\right\rvert} = \sum\limits_{k=1}^{n - 1} a_k \frac{\lambda_k^m}{\left\lvert\lambda_1^m\right\rvert} v_k =$

$= [a_1 \frac{\lambda_1^m}{\left\lvert\lambda_1^m\right\rvert} v_1 + a_{n - 1} \frac{\lambda_{n - 1}^m}{\left\lvert\lambda_1^m\right\rvert} v_{n - 1}] + \sum\limits_{k=2}^{n - 2} a_k \frac{\lambda_k^m}{\left\lvert\lambda_1^m\right\rvert} v_k =$

$= [a_1 \frac{\lambda_1^m}{\left\lvert\lambda_1^m\right\rvert} v_1 + a_{n - 1} \frac{\overline{\lambda_1}^m}{\left\lvert\lambda_1^m\right\rvert} v_{n - 1}] + \sum\limits_{k=2}^{n - 2} a_k \frac{\lambda_k^m}{\left\lvert\lambda_1^m\right\rvert} v_k$.

$= [a_1 (\frac{\lambda_1}{\left\lvert\lambda_1\right\rvert})^m v_1 + a_{n - 1} (\frac{\overline{\lambda_1}}{\left\lvert\lambda_1\right\rvert})^m \overline{v_1}] + \sum\limits_{k=2}^{n - 2} a_k \frac{\lambda_k^m}{\left\lvert\lambda_1^m\right\rvert} v_k$.

$= \left\lbrace a_1 (\frac{\lambda_1}{\left\lvert\lambda_1\right\rvert})^m v_1 + a_{n - 1} \overline{(\frac{\lambda_1}{\left\lvert\lambda_1\right\rvert})^m v_1}\right\rbrace + \sum\limits_{k=2}^{n - 2} a_k \frac{\lambda_k^m}{\left\lvert\lambda_1^m\right\rvert} v_k$.

По первой геометрической лемме первое слагаемое отображает $v_1$ в выпуклый многоугольник вписанный в эллипс с полуосями $\left\lvert a_1 \right\rvert + \left\lvert a_{n - 1} \right\rvert$ и $\left\lvert \left\lvert a_1 \right\rvert - \left\lvert a_{n - 1} \right\rvert \right\rvert$.
Второе слагаемое стремится к нулю так как $\lim\limits_{m \to \infty}(\frac{\lambda_k}{\left\lvert\lambda_1\right\rvert})^m = 0, k = 2, \dots, n - 2$.

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

Вывод
Так как мы ищем многоугольник который останется невыпуклым после любого $A^m$, то надо рассматривать только случай $\left\lvert a_1 \right\rvert = \left\lvert a_{n - 1} \right\rvert$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group