Уникальные триангуляционные двойники простых многоугольников

Учитывая триангуляцию (без точек Штейнера) простого многоугольника , можно рассмотреть дуал этой триангуляции, который определяется следующим образом. Мы создаем вершину для каждого треугольника в нашей триангуляции и соединяем две вершины, если соответствующие треугольники имеют общее ребро. Известно, что двойной граф является деревом с максимальной степенью три. $P$

Для моего приложения меня интересует следующее. Учитывая дерево с максимальной степенью три, есть всегда простой многоугольник такое , что сопряженное каждая триангуляция (без точек Штейнера) из равно . Здесь триангуляция может быть не единственной, но я требую, чтобы дуальный граф был уникальным. $T$ $P$ $P$ $T$ $P$

Это, конечно, верно, когда - путь, но становится неясным, когда у вас есть вершины третьей степени. $T$

reference-request computational-geometry Nizbel99
источник

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

orlp

Хороший улов! Я забыл упомянуть, что я не допускаю очки Штейнера в моих триангуляциях. Я обновлю вопрос.

Nizbel99

Интересный вопрос, но мне любопытно, какое приложение это может иметь. Ты можешь сказать?

Дискретная ящерица

Ответы:

Для дерева с максимальной степенью три, всегда ли существует простой многоугольник такой, что двойственное число каждой триангуляции (без точек Штейнера) равно ? $T$ $P$ $P$ $T$

Да. Чтобы показать это, я приведу процедуру, чтобы получить немного более сильный результат *:

Принимая во внимании дерева с максимальной степенью три, построить простой многоугольник , таким образом, что уникальные триангуляции из (без Steiner точки) имеет , как его сопряженные. $T$ $P$ $P$ $T$

$\Delta_0$ $v_0$ $T$ $v_0$ $Q$ $Q$

$v$
$w$ $AB$ $\Delta_v$ $D$ $AB$ $\Delta ABD$ $\Delta_w\leftarrow\Delta ABD$ $w$ $Q$

$P$ $T$

$AB$ $AD$

$CD$ $P$ $Q \notin \{B,D\}$ $DQ$ $P$ $AD$ $BD$ $\Delta ABD$ $Q$ существует, только если существует аналогичная точка для ранее размещенного треугольника. Поскольку такой точки для первого треугольника не существует, это означает, что такой точки нет ни для одного добавляемого треугольника.

$(X,Y)$ $P$ $XY$ $P$ $P$

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

_{*: Разница в том, что если мы интерпретируем «уникальный» как с точностью до изоморфизма (что согласуется с уникальностью триангуляций и двойственностей, отличающихся друг от друга), мы будем в порядке с многоугольником, имеющим множественные триангуляции, которые имеют изоморфные дуалы. Тем не менее, можно «прикрепить» больше треугольников к этим многоугольникам, чтобы некоторые дуалы больше не были изоморфными.}

Дискретная ящерица
источник