Dlaczego ósemki są używane do rozkładu przestrzeni wielobiegunowej?

18

W większości (wszystkich?) Implementacji szybkiej metody wielobiegunowej (FMM) do dekompozycji odpowiedniej domeny używa się oktetów. Teoretycznie oktany zapewniają proste wiązanie wolumetryczne, które jest przydatne do udowodnienia czasu działania O (n) FMM. Poza tym teoretycznym uzasadnieniem, czy istnieją korzyści z używania Octree w porównaniu do innych struktur danych drzewa lub trie?

Określenie listy interakcji może być łatwiejsze dzięki oktawie, ponieważ komórka zna swoich bezpośrednich sąsiadów. Lista interakcji jest jednak niepotrzebna przy użyciu bardziej dynamicznego przejścia przez drzewo, takiego jak Dual Tree Traversal .

Alternatywą byłoby drzewo KD. Jednym z możliwych teoretycznych minusów jest to, że konstrukcja wymaga kosztownej mediany operacji wyszukiwania. Istnieją jednak wersje drzewek Kd, które nie wymagają znalezienia mediany podczas budowy - aczkolwiek z mniej wydajnym dzieleniem przestrzeni. Pod względem implementacji drzewo kd jest bardzo proste.

Jeszcze bardziej radykalną alternatywą może być R-drzewo .

Moje pytanie brzmi więc: co jest w Octrees, które czynią z nich najlepszy wybór na FMM?

algorithms Ben Thompson
źródło
4
Myślę, że to szczególnie ułatwia ustalanie list interakcji (którzy obserwatorzy znajdują się w dalekim polu źródeł).
rchilton1980
Określenie list interakcji powinno być dość łatwe przy dowolnej formie hierarchicznego rozkładu przestrzeni.
Ben Thompson
1
Zgadzam się z tym, że ośmiornice są teoretycznie łatwe do analizy. Inne algorytmy szybkiego sumowania, takie jak macierze (które są algebraicznymi uogólnieniami FMM), wykorzystują różne drzewa, takie jak bisekcja geometryczna lub podział oparty na klastrach. H.
user2457602
1
Nie jestem w tym ekspertem, ale może fakt, że oktoty mają więcej „symetrii”, odgrywa pewną rolę? Przegrody w oktawie są rozmieszczone regularnie i mają ten sam kwadratowy kształt, co może pomóc w tworzeniu rozszerzeń wielobiegunowych w porównaniu np. Z drzewem kd.
Jannis Teunissen
Oktty są naturalnym wynikiem rozkładu domen w trzech wymiarach.
gpavanb

Odpowiedzi:

3

Powyższe komentarze podają kilka bardzo dobrych powodów, aby używać oktetów (tj. Rekurencyjnie zmniejszać o połowę kostkę obliczeniową w każdym wymiarze w przeciwieństwie do bardziej ogólnej bisekcji ortogonalnej). Dużą zaletą jest symetria i prostota obliczania list interakcji.

Twierdziłbym, że być może najważniejszą cechą, którą ósemki przynoszą do tabeli, jest to, że twierdzenie o dodatkowym gwarantowaniu FMM jest systematycznie spełnione dla interakcji dalekich stref niezależnych od geometrii z niezwykle prostym, dobrze oddzielonym kryterium jednego lub więcej „buforów” pudła. Innymi słowy, gwarantuje się, że reprezentacja sumy FMM pola potencjalnego zbiega się z rosnącym porządkiem w niepatologicznych okolicznościach.

smh
źródło