Критерии инвариантности плоской триангуляции Вороного-Делоне

[ilghiz]

Добрый день,

пусть у нас есть на плоскости набор точек. Мы по этому набору построили триангуляцию Вороного.

Пусть теперь мы эту плоскость, на которой у нас есть эти точки как-то повернули, и получили какую-то новую проекцию этих точек. Теперь построим триангуляцию. Я заметил, что эта триангуляция может как быть такой же, как и исходная, а иногда и отличная. С ходу нагуглить или вывести не получилось.

Скажите, пожалуйста, а есть ли какие-то критерии когда триангуляция сохраняется, а когда - нет.

Спасибо!

[пианист]

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

[ilghiz]

пианист в сообщении #1560665 писал(а):

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

Спасибо за ответ!

Я, кажется, не понятно выразился, я имел ввиду граф связанности этой триангуляции.

[svv]

ilghiz в сообщении #1560638 писал(а):

Пусть теперь мы эту плоскость, на которой у нас есть эти точки как-то повернули, и получили какую-то новую проекцию этих точек.

Пусть для простоты мы повернули плоскость на угол $\alpha$ вокруг прямой $\ell$, лежащей в плоскости.
Если рассматривать ситуацию относительно вращающейся плоскости, то новое множество точек, по которому строится триангуляция, получается из старого растяжением в $k=\cos\alpha$ раз относительно прямой $\ell$. Поскольку $|k|<1$, исключая повороты на $\pi n$, реально это сжатие.

В декартовых координатах, связанных с плоскостью, преобразование плоскости будет иметь вид $(x,y)\mapsto (x,ky)$, если ось $Ox$ совпадает с $\ell$.

Вы примерно так и рассматривали?

[ilghiz]

Спасибо большое, svv, за комментарий!

Не, я немного о другом имел ввиду. Пусть у нас есть плоскость, и на ней имеется набор точек $X=\{x_i\}_{i=1,\dots,N}, ~~ x_i \in {\mathbb R}^2$. Для этого набора точек построим триангуляцию Делоне, граф которой обозначим как $G_X$. Пусть у нас "хороший" набор точек, для которого $G_X$ будет единственным.

Теперь выполним трансформацию набора точек $X$ в $Y$ по формуле $y_i = A x_i + b, ~~ b \in {\mathbb R}^2, ~~ A \in {\mathbb R}^{2 \times 2}$ и для нового набора точек $Y$ построим триангуляцию Делоне, граф которой обозначим как $G_Y$.

Очевидно, что если $A$ - унитарная и для произвольного $b$ графы $G_X$ и $G_Y$ будут совпадать. Немного менее очевидно, но тоже легко показывается, что если $A = \alpha A'$, где $A'$ - унитарная, то графы тоже будут совпадать.

Есть примеров, когда точки $X$ расположены в углах декартовой сетки на прямоугольнике, когда для любой ненулевой $A$ графы тоже будут совпадать.

Но, в общем случае, если $X$ - какой-то произвольный набор, и $A$ - сильно скалирует точки по одному направлению, то графы перестают совпадать. И вот тут-то как раз хочется понять есть ли какие-то известные критерии, как это можно оценить до того, как строить саму триангуляцию...

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

Ну то есть любые идеи в какую сторону посмотреть, с большой радостью приветсвуются.

Спасибо!

[svv]

Общую задачу я понял, моё замечание касалось только трансформации точек при том повороте.
Конечно, Вы можете рассматривать общий случай $y=Ax+b$. Но в описанной ситуации разве $A$ не сведётся просто к сжатию плоскости? Проекции точек я считал ортогональными.

-- Сб июл 23, 2022 13:04:43 --

ilghiz в сообщении #1560638 писал(а):

пусть у нас есть на плоскости набор точек.

ilghiz в сообщении #1560638 писал(а):

Пусть теперь мы эту плоскость, на которой у нас есть эти точки как-то повернули, и получили какую-то новую проекцию этих точек.

Вот, всё по описанию.

[ilghiz]

Спасибо большое, svv, за ответ! Я, повидимому, не до конца понял Ваш ответ.

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

Но в описанной ситуации разве $A$ не сведётся просто к сжатию плоскости?

Не, вот смотрите. Пусть у нас точки на плоскости. Мы к ним построили граф. Теперь плоскость как-то покрутили, сдвинули влево-вправо, все пока идеально и граф не меняется.

А теперь плоскость наклоним к полю зрения. То есть у нас матрица трансформации будет вида

$$A = \left( \begin{tabular}{cc} $1$ & $0$ \\ $0$ & $\alpha$ \\ \end{tabular} \right),$$

где $\alpha$ - сильно отличается от единицы. Вот тут на многих наборах точек граф меняется, но, как я говорил, на точках в углах декартовых координат, граф не меняется.

[svv]

ilghiz в сообщении #1560853 писал(а):

То есть у нас матрица трансформации будет вида

$$A = \left( \begin{tabular}{cc} $1$ & $0$ \\ $0$ & $\alpha$ \\ \end{tabular} \right),$$

Ну да, у меня так же.

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

$(x,y)\mapsto (x,ky)$

Растяжение-сжатие относительно прямой я понимаю как тут.

[ilghiz]

Спасибо большое, svv, за ответ!

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

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

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

[svv]

А как же граф может не меняться (в общем случае), если он зависит от того, какие точки к данной являются ближайшими, а это меняется при масштабировании? (по одной оси)

[ilghiz]

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

А как же граф может не меняться (в общем случае), если он зависит от того, какие точки к данной являются ближайшими, а это меняется при масштабировании? (по одной оси)

Спасибо за ответ!

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

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

[svv]

ilghiz в сообщении #1560914 писал(а):

Грубо говоря, если взять равномерную треугольную сетку, то при обусловленности матрицы трансформации меньше 2, все всегда остается в порядке.

Я правильно понял, что при числе обусловленности меньше 2 Вы никогда не наблюдали изменение графа?
У меня получается, что для сетки, как на картинке, граф может меняться при числе обусловленности, заметно меньшем 2.

[ilghiz]

Спасибо большое, svv, за комментарий!

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

ilghiz в сообщении #1560914 писал(а):

Грубо говоря, если взять равномерную треугольную сетку, то при обусловленности матрицы трансформации меньше 2, все всегда остается в порядке.

Я правильно понял, что при числе обусловленности меньше 2 Вы никогда не наблюдали изменение графа?

да, именно этот пример имел ввиду

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

У меня получается, что для сетки, как на картинке, граф может меняться при числе обусловленности, заметно меньшем 2.

Скажите, пожалуйста, как это у вас получается? При обусловленности меньше 2, растяжение или сжатие треугольников бывает еще не сильно большое, и в окружности, сформированные треугольниками исходного графа после такого растяжения "не забегают" соседние точки. Или я что-то прозевал, скажите, пожалуйста?

[svv]

Возьмём две смежные ячейки сетки.

Каждая ячейка — правильный треугольник, сторону считаем единичной. Тогда высота каждой ячейки равна $\frac{\sqrt 3}{2}$.
Значит, $BC=1,\; AD=\sqrt 3$.

Сожмём плоскость по горизонтали в $\sqrt 3\approx 1.732$ раз. Тогда ромб $ABDC$ превратится в квадрат:

Здесь обе диагонали $A'D'$ и $B'C'$ единичны. Окружность, описанная вокруг $A'B'C'$, уже проходит через $D'$ — все эти точки лежат на одной окружности.

Если сжатие по горизонтали будет ещё на волосок больше, точка $D'$ попадёт внутрь окружности, и триангуляция разрушится:

[ilghiz]

Спасибо большое, svv,

ой, точно, я с обусловленностью в 2 просчитался... подразуменвая $\sqrt2$ - где-то что-то в квадрат, думаю, забыл возвести.

Похоже, что все другие наборы сеток, кроме прямоугольной, будут вести себя еще хуже, то есть фактически как не старайся, придумать сетку, на которой граф Делоне триангуляции сохраняется для большого числа обусловленности матрицы трансформации, повидимому, нельзя. Тогда понятно, почему этот факт в литературе не обсуждался.