Unikalne dualne triangulacje prostych wielokątów

Biorąc pod uwagę triangulację (bez punktów Steinera) prostego wielokąta , można rozważyć podwójność tej triangulacji, która jest zdefiniowana następująco. Tworzymy wierzchołek dla każdego trójkąta w naszej triangulacji i łączymy dwa wierzchołki, jeśli odpowiednie trójkąty mają wspólną krawędź. Podwójny wykres jest znany jako drzewo o maksymalnym stopniu trzecim.$P$

W przypadku mojej aplikacji interesują mnie następujące kwestie. Biorąc pod drzewem z maksymalnym stopniu trzy, tam jest zawsze prosty wielokąta takie, że podwójny każdego triangulacji (bez punktów Steiner) z jest równa . Tutaj triangulacja może nie być unikalna, ale wymagam, aby podwójny wykres był unikalny.$T$$P$$P$$T$$P$

Z pewnością jest to prawdą, gdy jest ścieżką, ale staje się niejasne, gdy masz wierzchołki stopnia trzeciego.$T$

Biorąc pod uwagę drzewo o maksymalnym stopniu trzecim, czy zawsze istnieje prosty wielokąt taki, że podwójność każdej triangulacji (bez punktów Steinera) jest równa ?$T$$P$$P$$T$

Tak. Aby to pokazać, podam procedurę uzyskania pozornie nieco silniejszego wyniku *:

Biorąc pod drzewem z maksymalnym stopniu trzy, skonstruować prosty wielokąta tak, że wyjątkowy triangulacji z (bez Steiner punktów) ma jak jego podwójny.$T$$P$$P$$T$

Najpierw tworząc wstępną trójkąta , co stanowi około wierzchołek w i dodać do kolejki . Następnie powtarzaj następujące czynności, aż będzie puste:$\Delta_0$$v_0$$T$$v_0$$Q$$Q$

• Usuń górny element, , z kolejki.$v$
• Dla każdego sąsiadującego wierzchołka , dla którego nie umieściliśmy jeszcze trójkąta, wybierz bok trójkąta i punkt wewnątrz obszarów stożkowych generowanych przez linię przechodzącą przez i jego sąsiednie segmenty, tak że trójkąt nie przecina żadnych innych trójkątów. (Patrz poniżej), utworzony dodać celu .$w$$AB$$\Delta_v$$D$$AB$$\Delta ABD$$\Delta_w\leftarrow\Delta ABD$$w$$Q$

Ten obraz podaje przykład możliwego wielokąta (po lewej) dla danego (po prawej)$P$$T$

Aby zobaczyć, dlaczego ta procedura działa, należy najpierw zauważyć, że po utworzeniu nowego trójkąta segmenty i generują stożek, który ma niepusty obszar nie przecinający się z istniejącymi trójkątami (patrz także poprzedni rysunek), dzięki czemu możemy znaleźć odpowiedni punkt na każdym kroku i stwórz wielokąt.$AB$$AD$

Po drugie, wybraliśmy trójkąty tak, że odcinek między nie całkowicie znajdują się wewnątrz . Jeśli istnieje punkt narożny już umieszczonych trójkątów, taki że jest całkowicie w , to musi leżeć w stożkach wygenerowanych przez i . Ponieważ jednak część tego stożka, która nie leży wewnątrz jest zawarta w stożku wygenerowanym przez wcześniej umieszczony trójkąt, taki$CD$$P$$Q \notin \{B,D\}$$DQ$$P$$AD$$BD$$\Delta ABD$$Q$istnieje tylko wtedy, gdy istnieje analogiczny punkt dla wcześniej umieszczonego trójkąta. Ponieważ nie istnieje taki punkt dla pierwszego trójkąta, oznacza to, że nie ma takiego punktu dla żadnego dodanego trójkąta.

Oznacza to, że wszystkie pary dowolnego punktu narożnego dla którego segment jest całkowicie zawarty w są już w skonstruowanej triangulacji, więc triangulacja jest unikalna dla (wszystkie triangulacje dodają tę samą liczbę segmentów wewnętrznych )$(X,Y)$$P$$XY$$P$$P$

Zauważ, że wielokąty zbudowane tą metodą mają zwykle ostre kąty. Podejrzewam, że dowolne duże wykresy wymagają wielokątów o dowolnych małych kątach, co może stanowić problem przy rysowaniu tych wielokątów ze skończoną precyzją.

_{*: Różnica polega na tym, że jeśli interpretujemy „unikatowy” jako aż do izomorfizmu (co jest zgodne z wyjątkowością triangulacji i różnic podwójnych, które są różne), bylibyśmy w porządku z wielokątem posiadającym wiele triangulacji, z których wszystkie mają izomorficzne podwójne. Możliwe jest jednak „dołączenie” więcej trójkątów do tych wielokątów, aby upewnić się, że niektóre elementy dualne nie są już izomorficzne.}