Osadzanie tutte

W rysowaniu grafów i teorii grafów geometrycznych osadzanie Tutte lub osadzanie barycentryczne prostego , płaskiego wykresu połączonego z trzema wierzchołkami jest osadzeniem linii prostej bez przecinania, z właściwościami polegającymi na tym, że zewnętrzna ściana jest wypukłym wielokątem i że każde wnętrze wierzchołek jest uśredniony (lub środek ciężkości) pozycji sąsiadów. Jeśli zewnętrzny wielokąt jest ustalony, ten warunek na wewnętrznych wierzchołkach określa ich położenie jednoznacznie jako rozwiązanie układu równań liniowych . Rozwiązanie równań geometrycznie daje planarne osadzenie . Twierdzenie Tutte'a o sprężynie , udowodnione przez WT Tutte ( 1963 ) stwierdza, że ​​to unikalne rozwiązanie jest zawsze wolne od krzyżowania, a co ważniejsze, każda ściana wynikowego płaskiego osadzania jest wypukła. Nazywa się to twierdzeniem o sprężynie, ponieważ takie osadzenie można znaleźć jako położenie równowagi dla układu sprężyn reprezentujących krawędzie wykresu.

Przykład

Tutte osadzanie wykresu sześcianu. Zewnętrzne cztery wierzchołki są ustalone w rogach kwadratu jednostkowego , a każdy pozostały wierzchołek znajduje się w średniej pozycji swoich sąsiadów.

Niech G będzie wykresem sześcianu i (wybierając jedną z jego ścian czworobocznych jako ścianę zewnętrzną) ustal cztery wierzchołki ściany zewnętrznej w czterech rogach kwadratu jednostkowego , punkty, których współrzędne x i y są wszystkimi czterema kombinacjami zero i jeden. Następnie, jeśli pozostałe cztery wierzchołki zostaną umieszczone w czterech punktach, których x i y są kombinacjami 1/3 i 2/3, jak na rysunku, wynikiem będzie osadzenie Tutte. Ponieważ w każdym wierzchołku wewnętrznym v osadzania, a dla każdej z dwóch współrzędnych trzej sąsiedzi v mają wartości współrzędnych równe v , mniejsze o 1/3 i większe o 1/3; średnia z tych wartości jest taka sama jak wartość współrzędnej samego v .

Układ równań liniowych

Warunek, że wierzchołek v znajduje się w średniej pozycji swoich sąsiadów, można wyrazić za pomocą dwóch równań liniowych , jednego dla współrzędnej x v i drugiego dla współrzędnej y v . Dla wykresu z n wierzchołkami, z których h jest ustalonych na zewnętrznej powierzchni, istnieją dwa równania dla każdego wierzchołka wewnętrznego, a także dwie niewiadome (współrzędne) dla każdego wierzchołka wewnętrznego. Dlatego daje to układ równań liniowych z 2( n − h ) równań z 2 ( n − h ) niewiadomymi, których rozwiązaniem jest osadzenie Tutte'a. Jak Tutte (1963) , dla grafów planarnych połączonych z trzema wierzchołkami system ten nie jest zdegenerowany. Dlatego ma unikalne rozwiązanie, a (przy ustalonej zewnętrznej powierzchni) wykres ma unikalne osadzenie Tutte. To osadzenie można znaleźć w czasie wielomianowym , rozwiązując układ równań, na przykład stosując eliminację Gaussa .

Reprezentacja wielościenna

Zgodnie z twierdzeniem Steinitza 3-spójne grafy planarne, do których stosuje się twierdzenie Tutte'a o sprężynie, pokrywają się z grafami wielościennymi , grafami utworzonymi przez wierzchołki i krawędzie wypukłego wielościanu . Zgodnie z korespondencją Maxwella – Cremony dwuwymiarowe osadzenie płaskiego wykresu tworzy pionowy rzut trójwymiarowego wypukłego wielościanu wtedy i tylko wtedy, gdy osadzenie ma naprężenie równowagi , przypisanie sił do każdej krawędzi (wpływające na oba punkty końcowe w równych i przeciwnych kierunkach równoległych do krawędzi) w taki sposób, że siły znoszą się w każdym wierzchołku. W przypadku osadzania Tutte przypisanie każdej krawędzi siły przyciągania proporcjonalnej do jej długości (jak sprężyna) powoduje zniesienie sił we wszystkich wierzchołkach wewnętrznych, ale niekoniecznie jest to naprężenie równowagi w wierzchołkach zewnętrznego wielokąta. Jednakże, gdy zewnętrzny wielokąt jest trójkątem, możliwe jest przypisanie sił odpychających do jego trzech krawędzi, aby również tam siły się zniosły. W ten sposób osadzania Tutte mogą być użyte do znalezienia diagramów Schlegla każdego wypukłego wielościanu . Dla każdego 3-spójnego płaskiego wykresu G , albo sam G , albo podwójny wykres G ma trójkąt, więc albo daje to wielościenną reprezentację G , albo jego podwójną; w przypadku, gdy wykres podwójny jest tym z trójkątem, polaryzacja daje wielościenną reprezentację samego G.

Zastosowania w przetwarzaniu geometrii

$geometrii$$osadzanie$ Tutte jest używane do parametryzacji uv powierzchni 3D w przypadkach gdzie topologia powierzchni pozostaje taka sama w poprzek i ${ \ Displaystyle {\ mathcal$$S}} ^ {*}}$ (topologia dysku). Metoda Tutte'a minimalizuje całkowitą energię zniekształcenia sparametryzowanej przestrzeni, traktując każdy przekształcony wierzchołek jako masę punktową, a krawędzie w poprzek odpowiednich wierzchołków jako sprężyny. Naprężenie każdej sprężyny jest określone przez długość krawędzi w oryginalnej powierzchni 3D, aby zachować kształt. Ponieważ rozsądne jest posiadanie mniejszych sparametryzowanych długości krawędzi dla mniejszych krawędzi $}$ większych sparametryzowanych długości krawędzi dla większych krawędzi $}$ , stałe sprężystości ${$$}$ są zwykle traktowane jako odwrotność bezwzględnej odległości między wierzchołkami przestrzeni 3D.

${\ Displaystyle {\ tekst {Energia zniekształceń}} ~ E = \ Sigma _ {(i, j) \ in E ({\ mathcal {S}})} ~ w_ {ij} ~ \ | {\ textbf {u}}_{\text{i}}-{\textbf {u}}_{\text{j}}\|^{2}{\text{, gdzie }}w_{ij}={\frac {1}{\|{\textbf {v}}_{\text{i}}-{\textbf {v}}_{\text{j}}\|}}{\text{, }}\{ {\textbf {u}}_{\text{i}}\}\in {\mathcal {S}}^{*}{\text{, }}\{{\textbf {v}}_{\text {i}}\}\w {\mathcal {S}}}$

gdzie $reprezentuje$ powierzchni 3D Gdy wagi są dodatnie (jak w powyższym przypadku), gwarantuje się, że odwzorowanie jest bijekcyjne $bez$ Ale kiedy nie stosuje się żadnych dalszych ograniczeń, rozwiązanie, które minimalizuje energię zniekształcenia, w trywialny sposób zapada się w pojedynczy punkt w sparametryzowanej przestrzeni.

Dlatego należy podać warunki brzegowe, w których zbiór znanych wierzchołków powierzchni 3D jest odwzorowywany na znane punkty w sparametryzowanej przestrzeni 2D. Jednym z powszechnych sposobów wyboru takich warunków brzegowych jest rozważenie wierzchołków na największej pętli granicznej oryginalnej powierzchni 3D, którą można następnie ograniczyć do odwzorowania na zewnętrzny pierścień dysku jednostkowego w sparametryzowanej przestrzeni 2D. Należy zauważyć, że jeśli powierzchnia 3D jest rozmaitością, krawędzie graniczne można wykryć, sprawdzając, czy należą one tylko do jednej powierzchni siatki.

Zastosowania parametryzacji w grafice i animacji obejmują między innymi mapowanie tekstur.

Uogólnienia

Colin de Verdière (1991) uogólnił twierdzenie Tutte'a o sprężynie na grafy na powierzchniach wyższego rodzaju z niedodatnią krzywizną , gdzie krawędzie są reprezentowane przez geodezję ; wynik ten został później niezależnie ponownie odkryty przez Hassa i Scotta (2015) . Analogiczne wyniki dla grafów osadzonych na torusie zostały niezależnie udowodnione przez Delgado-Friedrichs (2005) , Gortlera, Gotsmana i Thurstona (2006) oraz Lovásza (2019) .

Chilakamarri, Dean i Littman (1995) badają osadzanie trójwymiarowych grafów grafów czterowymiarowych polytopów , utworzony tą samą metodą, co osadzanie Tutte'a: wybierz jeden aspekt polytope jako zewnętrzną powierzchnię trójwymiarowego osadzania i zamocuj jego wierzchołki na miejscu jako wierzchołki trójwymiarowego wielościanu w przestrzeni. Niech każdy pozostały wierzchołek polytopu będzie mógł swobodnie poruszać się w przestrzeni i zastąp każdą krawędź polytopu sprężyną. Następnie znajdź konfigurację o minimalnej energii układu sprężyn. Jak pokazują, otrzymany w ten sposób układ równań znów jest niezdegenerowany, ale nie jest jasne, w jakich warunkach ta metoda znajdzie osadzenie realizujące wszystkie aspekty politopu jako wielościany wypukłe.

Powiązane wyniki

Wynik, zgodnie z którym każdy prosty graf planarny można narysować z prostymi krawędziami, nazywa się twierdzeniem Fáry'ego . Twierdzenie Tutte Spring dowodzi tego dla 3-spójnych grafów planarnych, ale wynik jest bardziej prawdziwy dla grafów planarnych niezależnie od łączności. Użycie systemu sprężyn Tutte dla wykresu, który nie jest spójny 3, może skutkować degeneracjami, w których podwykresy danego grafu zapadają się na punkt lub odcinek linii; jednakże dowolny wykres planarny można narysować za pomocą osadzania Tutte, dodając dodatkowe krawędzie, aby uzyskać połączenie 3, rysując wynikowy wykres 3-połączony, a następnie usuwając dodatkowe krawędzie.

Graf jest spójny k -wierzchołkowo , ale niekoniecznie planarny, wtedy i tylko wtedy, gdy ma wypukłe osadzenie w ( k -1)-wymiarowej przestrzeni, w której dowolna k -krotka wierzchołków jest umieszczona na wierzchołkach simpleksu i , dla każdego pozostałego wierzchołka v , wypukła powłoka sąsiadów v jest pełnowymiarowa z v w swoim wnętrzu. Jeśli takie osadzenie istnieje, można je znaleźć, ustalając położenie wybranego k wierzchołków i rozwiązywanie układu równań, który umieszcza każdy wierzchołek jako średnią swoich sąsiadów, tak jak w planarnym osadzeniu Tutte'a.

W generowaniu siatki elementów skończonych wygładzanie Laplaca jest powszechną metodą przetwarzania końcowego wygenerowanej siatki w celu poprawy jakości jej elementów; jest szczególnie popularny w przypadku siatek czworobocznych , dla których inne metody, takie jak algorytm Lloyda do wygładzania siatek trójkątnych, mają mniejsze zastosowanie. W tej metodzie każdy wierzchołek jest przesuwany do lub w kierunku średniej pozycji sąsiadów, ale ruch ten jest wykonywany tylko dla niewielkiej liczby iteracji, aby uniknąć dużych zniekształceń rozmiarów elementów lub (w przypadku niewypukłych domen siatki ) splątane niepłaskie siatki.

rysowania grafów kierowane siłą są nadal popularną metodą wizualizacji grafów, ale systemy te zwykle wykorzystują bardziej skomplikowane układy sił, które łączą siły przyciągania na krawędziach grafu (jak w osadzeniu Tutte'a) z siłami odpychania między dowolnymi parami wierzchołków. Te dodatkowe siły mogą spowodować, że system będzie miał wiele stabilnych lokalnie konfiguracji, a nie, jak w osadzeniu Tutte'a, jedno globalne rozwiązanie.