Odzyskiwanie punktu osadzania z wykresu z krawędziami ważonymi odległością punktu

Załóżmy, że podam ci niekierowany wykres z ważonymi krawędziami i powiem, że każdy węzeł odpowiada punktowi w przestrzeni 3D. Ilekroć pomiędzy dwoma węzłami jest krawędź, ciężar krawędzi jest odległością między punktami.

Twoim celem jest zrekonstruowanie względnych pozycji punktów, biorąc pod uwagę tylko dostępne odległości (reprezentowane przez wagi krawędzi). Na przykład, jeśli dałem ci , wtedy wiesz, że punkty są wierzchołkami czworościanu. Nie wiesz, gdzie jest on związany z początkiem, czy jego orientacją, czy też został odbity, ale możesz powiedzieć, że to czworościan.$d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$

Zasadniczo problem jest prosty, jeśli podam wszystkie długości krawędzi. Wystarczy dowolnie wybrać punkt który ma być , następnie wybrać sąsiedni punkt i ustawić go na , a następnie wspólny sąsiad zostaje triangulowany na XY płaszczyźnie, wtedy ostatni wspólny sąsiad zostaje triangulowany do półprzestrzeni i przerywa pozostałą symetrię (zakładając, że nie wybrałeś punktów zdegenerowanych). Możesz użyć tych czterech punktów do triangulacji wszystkich pozostałych. ( 0 , 0 , 0 $p_0$$(0,0,0)$ ( d 0 , 1 , 0 , 0 ) p 2 p 3 z > $p_1$$(d_{0,1},0,0)$$p_2$$p_3$$z > 0$

Z drugiej strony, gdy brakuje niektórych długości krawędzi, odzyskanie osadzenia może być niemożliwe. Na przykład, jeśli istnieje wierzchołek, który rozłącza wykres podczas cięcia, wówczas dwa komponenty, które oddzieliłby, gdyby zostały usunięte, mogą się obracać względem siebie.

Co rodzi pytania:

• Ile kosztuje znalezienie rozwiązania?
• Jak ustalić, czy rozwiązanie jest unikalne, aż do tłumaczenia / rotacji / kopii lustrzanej? Czy łączność 3 jest wystarczająca? Niezbędny?
• Jakie warunki sprawiają, że problem jest trywialny?
• Jeśli nie obiecuję, że wagi krawędzi faktycznie odpowiadają punktowi sinus odległości 3d, jak drogie jest ustalenie, czy osadzenie jest w ogóle możliwe?

Jedno algorytmiczne podejście do rozwiązania tego problemu: potraktuj to jako zestaw węzłów połączonych sprężynami, a następnie pozwól im się uspokoić / zrelaksować w kształcie.

Każda krawędź odpowiada sprężynie; jeśli odległość między punktami i ma wynosić , wówczas wybierana jest sprężyna, więc idealnie chce mieć długość (może być dłuższa lub krótsza, ale to kosztuje energię ). Teraz chcemy rozwiązać zestaw pozycji, które minimalizują całkowitą energię. Załóżmy, że każdy wierzchołek jest umieszczony w punkcie . Wtedy całkowita energia tego układu będzie wynosićv w d v , w d v , w v x v ∈ R$(v,w)$$v$$w$$d_{v,w}$$d_{v,w}$$v$$x_v \in \mathbb{R}^3$

Tutaj podano (są to ciężary na krawędziach), a my chcemy rozwiązać dla (są to współrzędne punktów). x $d_{v,w}$$x_v$

Możemy rozwiązać układ który minimalizuje tę całkowitą energię. Taki układ zapewnia następnie rozsądnego kandydata na pozycje punktów. Jest to problem optymalizacji i istnieją standardowe techniki rozwiązywania tego rodzaju problemu optymalizacji. Zobacz np. Artykuł Network Solutions autorstwa Erici Klarreich.$x$

Nie sądzę, że istnieje jakakolwiek gwarancja, że ​​zapewni to prawidłowe pożądane rozwiązanie. Możliwe, że problem z optymalizacją ustabilizuje się na innym optymalnym, który nie odzwierciedla faktycznego rozmieszczenia poszukiwanych punktów. Jednak jeśli twój wykres jest wystarczająco gęsty, podejrzewam, że często może działać i dać pożądane rozwiązanie.

Przypis: Oczywiście nawet w najlepszym przypadku możemy rozwiązać ten problem tylko do tłumaczenia, obrotu i odbicia, ponieważ te transformacje zachowują wszystkie odległości. Dlatego nie możesz oczekiwać wyjątkowego rozwiązania - możesz jednak mieć nadzieję, że rozwiązanie będzie unikalne pod względem tłumaczenia, rotacji i refleksji.

Na koniec jest dużo pracy nad osadzaniem wykresów w przestrzeni , przy jednoczesnym minimalizowaniu zniekształceń osadzania. To bardzo powiązane; zasadniczo pytasz o osadzenie zerowego zniekształcenia w . Zatem techniki opracowane w tym kontekście mogą być przydatne również w przypadku twojego problemu. Zazwyczaj praca ta koncentruje się na znalezieniu osadzenia o niskim zniekształceniu, ponieważ praca ta koncentruje się na przypadku, w którym nie ma idealnego osadzenia, które sprawia, że ​​wszystkie odległości są dokładnie dopasowane, dlatego zamiast tego szuka rozwiązania o niskim zniekształceniu (takiego, w którym występuje największe odległości od krawędzi pasuje całkiem dobrze) - dzięki czemu praca koncentruje się na nieco innym problemie. Jednak możliwe jest, że ich techniki mogą być skuteczne również w twojej sytuacji. Warto spróbować.ℓ $\ell_2$$\ell_2$

Problem dotyczy NP-Complete . Pozycje punktów są dobrym certyfikatem, więc są w NP i można zakodować obwody w „czy jest zadowalający zestaw punktów?” problem.

Redukcja z oceny obwodu do osadzania na odległość

Zamierzamy zredukować ocenę obwodu do problemu osadzania odległości, tworząc układ współrzędnych, umieszczając w nim logiczne bity, wyrównując bity okablowania i tworząc widżety dla bramek NOT i AND.

1. Współrzędne . Potrzebujemy pewnego rodzaju układu współrzędnych, za pomocą którego możemy pozycjonować punkty. Zrób to, tworząc „bazowy” czworościan punktów. Dodaj cztery punkty, wszystkie zadeklarowane jako odległość od siebie. Zmusza to kształt tych czterech punktów do czworościanu. Możemy pozycjonować inne punkty względem naszego układu współrzędnych czworościanu, określając ich odległość do każdego z czterech rogów podstawy. Czworościan może być tłumaczony, obracany i odbijany, ale to samo stanie się z wszystkimi innymi punktami.$1$

2. Bity . Żeby trochę zrobić, ustawiamy trójkąt punktów względem czworościanu podstawy. Norma trójkąta musi być skierowana w górę wzdłuż osi Z, tak aby trójkąt był równoległy do ​​płaszczyzny XY (we współrzędnych czworościanu). Również jego krawędzie muszą mieć długość . Po tym dodamy punkt „wartości” , określony jako odległość od pozostałych trzech. My nie łączyć do podstawy układu współrzędnych. Daje to dwie możliwe pozycje: wyśrodkowany powyżej lub poniżej trójkąta, jako ostatni róg czworościanu. Bit jest WŁĄCZONY, jeśli punkt znajduje się powyżej trójkąta, i WYŁĄCZONY, jeśli jest poniżej.v 1 v $1$$v$$1$$v$$\frac{1}{\sqrt{3}}$

3. Przewody . Możemy zmusić dwa bity do równości, mówiąc, że odległość między ich punktami wartości jest równa odległości między środkami ich trójkątów. Jest jeden wyjątek: kiedy górny lub dolny róg jednego z bitów dokładnie pokrywa się z płaszczyzną środkową drugiego. W takim przypadku najpierw używamy drutu, aby przesunąć jeden z bitów w pionie.

4. NIE . Możemy trochę zanegować, dodając drugi punkt wartości do tego samego trójkąta, ale wymagając, aby było w odległości od . To zmusza do zajęcia pozycji przeciwnej do względem trójkąta, dając nam nieco przeciwną wartość.w $w$$w$ vw$\frac{2}{\sqrt{3}}$$v$$w$$v$

5. IMPLIKACJE . Równie odległe zagadnienie, które musieliśmy obejść z przewodami, jest w rzeczywistości całkiem przydatne. Kiedy bity ustawiają się w taki sposób, co możemy wymusić pionowym drutem, im wyższy, tym niższy. Jeśli prawda jest wyższa, tylko górna część dolnej jest w odpowiedniej odległości. Jeśli wyższy jest fałszywy, zarówno górna, jak i dolna są w odpowiedniej odległości.

6. I . Aby bit był równy i , potrzebujemy dwóch implikacji i widgetu, aby wymusić równość, gdy i zgadzają. Konsekwencje są tylko i . Aby utworzyć widżet, przesuwamy i pionie, aby znajdowały się na tym samym poziomie i odległości od siebie, a następnie przesuwamy aby był między nimi jednakowy odstęp . Następnie dodajemy punkty i w odległości od iA B A B $C$$A$$B$$A$$B$$C \implies A$A B $C \implies B$$A$$B$ CSASB$\frac{2}{\sqrt 3}$$C$$S_A$$S_B$ ABSASB$\frac{\sqrt 2 - 1}{2 \sqrt 3}$$A$$B$odpowiednio punkty wartości i wymuszają, aby odległość między i wynosiła . Dodajemy również punkt odległość zarówno od jak i . Tworzy to łańcuch między punktami wartości i , z w środku łańcucha. Kiedy , łańcuch jest rozciągnięty do granicy, a znajduje się w środku trójkątaGdy , ogniwa łańcucha są zmuszone do poruszania się dokładnie w przeciwnych kierunkach, pchając$S_A$$S_B$ SC$\frac{\sqrt 2 + 1}{\sqrt 3}$$S_C$ SASBABSCA≠BSCCA=BSCCACSD$\frac{\sqrt 2 + 1}{2 \sqrt 3}$$S_A$$S_B$$A$$B$$S_C$$A \neq B$$S_C$$C$$A = B$do granicy i umieszczając na punkt wartości równymi . Aby wymusić punkt wartości , wstawiamy punkt odległość zarówno od punktu wartości jak iNie ogranicza punkt wartość jest kiedy , ale siły , gdy .$S_C$$C$$A$$C$$S_D$ SCCCA≠BA=B=CA=$\frac{1}{2 \sqrt 3}$$S_C$$C$$C$$A \neq B$$A=B=C$$A=B$

Za pomocą tych elementów można zakodować dowolny obwód w celu osadzenia na odległość. Wejścia stają się bitami, bramki rozkładają się na NOT, a AND wprowadzają nowe bity w razie potrzeby i to wszystko. Wymuś, aby pozycja wyjściowa była prawdziwa, a otrzymasz problem dotyczący satysfakcji.

Częściowa odpowiedź na wyjątkowość : 3-łączność nie jest wystarczająca.

$Q_3$

$Q_3$

Weź rogi kartonowego pudełka, aby być wierzchołkami zainteresowania. Każdy róg kartonu ma ustaloną odległość od innych narożników, z którymi ma wspólną powierzchnię pudełka.

$Q_3$

jest to znane jako następujący problem i występuje np. przy rekonstrukcji współrzędnych z sieci czujników, które mogą mierzyć odległość do pobliskich węzłów, a ten dokument może służyć jako mini-ankieta wraz z wiodącym algorytmem (algorytmami). wiodąca metoda znana jest jako projekcja wartości pojedynczej, kolejna progresja wartości pojedynczej. algorytmy są ogólnie oparte na algebrze macierzowej i redukcji rang. artykuł implementuje oba algorytmy i podaje analizę empiryczną.

Euklidesowa odbudowa odległości z częściowej informacji o odległości Xu, Chen