Przykłady, w których wgląd w geometrię był przydatny do rozwiązania czegoś całkowicie niegeometrycznego

Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o obliczeniach o punktach w 3-d, które można następnie rozwiązać za pomocą naszej intuicji dotyczącej przestrzeni. Wydaje się to sugerować, że czasami powinno być możliwe rozwiązanie całkowicie nie geometrycznego problemu przy użyciu technik z geometrii. Czy ktoś wie o takich przykładach?

Oczywiście terminy „geometryczny” i „nie geometryczny” są tutaj nieco niejasne. Można argumentować, że każdy problem geometryczny jest w rzeczywistości nie geometryczny, jeśli zastąpisz wszystkie punkty ich współrzędnymi. Ale intuicyjnie definicja jest jasna. Powiedzmy, że nazywamy coś geometrycznego, gdybyśmy rozważyli wysłanie artykułu na ten temat do SoCG.

Kilka innych przykładów:

Sleator, Thurston i Tarjan zastosowali geometryczną reprezentację drzew jako części wielokątów i geometrię hiperboliczną, aby udowodnić dolne granice rotacji drzewa binarnego . (Uważam również, że historię drzewa dynamicznych wyszukiwań binarnych można przedstawić jako czworościan.)

Zmniejszenie najmniej powszechnego przodka do zakresu minimalnych zapytań , ze względu na Berkmana i Vishkina, wiąże problem struktur danych na drzewach z problemem prawdopodobnie geometrycznym. (i dzięki za artykuł David)

Ograniczenie problemu szeregowania do niezależnego od masy zestawu prostokątów równoległych do osi [1] lub ograniczenie innego problemu szeregowania do pokrycia zestawu geometrycznego [2] może się kwalifikować.

Zmniejszenie największego powszechnego problemu podsekwencji do znajdowania warstw maksimów jest dobrze znane (co oznacza, że ​​jestem zbyt leniwy, by spojrzeć na to, kto o tym pomyślał).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor i Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. Geometria planowania, FOCS 2010.

[późniejsza edycja] Kilka innych przypadków, w których „geometryczny” widok wydawał się zaskakujący (chociaż standardy „poddanie się SoCG” lub „robi coś do wizualizacji” prawdopodobnie nie są spełnione):

algebraiczna topologia zastosowana do dolnych granic obliczeń rozproszonych

włączenie obliczalności do wymiaru Hausdorffa

zdefiniowanie pojęcia odległości dla grup, następnie objętości, następnie wzrostu objętości jako funkcji odległości, a następnie użycie „wzrostu wielomianowego”

$\ell_1$

Zostały one również wymienione gdzieś indziej, ale przykład, który podoba mi się to: sortowanie z częściowymi informacjami to problem znalezienia ustalonego nieznanego rozszerzenia liniowego zbioru, biorąc pod uwagę ten zestaw i używając liczby zapytań porównawczych jak najbliżej teorii informacji dolna granica (to tylko sortowanie, gdy liczba porównań jest krytyczną miarą złożoności, a niektóre porównania podano za darmo). Istnienie optymalnych (aż do stałych) strategii porównawczych zostało udowodnione przez Saksa i Kahna przy użyciu właściwości polytopu porządkowego, specjalnego polytopu związanego z zestawem (można znaleźć świetną ekspozycję w książce Matousek's Lectures on Discrete Geometry). Pierwszy algorytm czas wielomian (Kahna i Kima), który oblicza optymalną (aż do stałej) strategię porównywania, ponownie użył właściwości polytopu rzędu, a także stabilnego zestawu polytopów wykresu nieporównywalności zestawu wejściowego.

Istnieje stosunkowo niedawna praca Demaine i wsp. , Która wykorzystuje geometryczną reprezentację drzew binarnych do wyszukiwania, aby rozwijać najnowszą technologię dynamicznej optymalności. Jestem tu trochę niejasny, ponieważ nie rozwiązują przypuszczeń DO: ale wzmacniają pewne granice i dają nowe spojrzenie, które wydają się pochodzić z formuły geometrycznej.

Nie sądzę, żeby były przykłady takich rzeczy. Z wyjątkiem programowania liniowego, programowania półokreślonego, liczb zespolonych, dużych części uczenia maszynowego itp. Prawdziwe pytanie brzmi: http://www.youtube.com/watch?v=ExWfh6sGyso .

W zeszłym roku na POPL pojawił się miły artykuł, EigenCFA: Analiza przyspieszania przepływu za pomocą układów GPU , które reprezentowały warunki lambda jako macierze, a następnie używały układów GPU do szybkiego wykonywania na nich analizy przepływu danych.

W artykule nie wskazano tego wprost, ale w zasadzie robili to, wykorzystując kategoryczną strukturę przestrzeni wektorowych do reprezentowania drzew. Oznacza to, że w zwykłej teorii zbiorów drzewo (o pewnej stałej wysokości) jest zagnieżdżonym rozłącznym połączeniem produktów kartezjańskich.

Jednak przestrzenie wektorowe mają również bezpośrednie iloczyny i sumy, więc możesz reprezentować drzewo jako element odpowiedniej przestrzeni wektorowej. Co więcej, produkty bezpośrednie i sumy bezpośrednie pokrywają się dla przestrzeni wektorowych - tzn. Mają taką samą reprezentację. Otwiera to drzwi do równoległych implementacji: ponieważ fizyczne reprezentacje są takie same, można wyeliminować wiele rozgałęzień i pogoni za wskaźnikami.

Wyjaśnia również, dlaczego analiza przepływu danych jest czasem sześciennym: oblicza wektory własne!

W sieciach, routery używają TCAM (trójskładnikowe pamięci adresowane treścią - innymi słowy, pamięć adresowalna treści z nieistotnym bitem) do klasyfikowania ruchu. Wpisy w TCAM są często wielowymiarowymi regułami dopasowywania prefiksów: na przykład (101 *, 11 *, 0 *) pasuje do dowolnego pakietu, w którym pierwsze pole nagłówka zaczyna się od 101, a drugie pole nagłówka zaczyna się od 11 (i itp.) Jeśli pakiet nie pasuje do pierwszej reguły, przechodzi do drugiej i tak dalej, aż do znalezienia pasującej reguły.

$d$$R^{d+1}$$d+1$$R^{d+1}$$d$$d+1$

Dla ludzi tworzących sieci interpretacja ta jest przydatna do zrozumienia, co robi określony zestaw reguł. Dla teoretyków istnieją inne ciekawe zastosowania. Według algorytmów klasyfikacji pakietów autorstwa Gupty i McKeown interpretacja geometryczna pozwoliła nam szybko ustalić dolne i górne granice dla problemu klasyfikacji pakietów. Wiem, że praca nad minimalizacją reguł TCAM (znajdowanie najmniejszej liczby reguł, która zachowuje semantykę) również skorzystała z podejścia geometrycznego. Istnieje mnóstwo referencji, które mógłbym podać w tym zakresie, ale ten, który może być dla Ciebie najbardziej użyteczny, to Applegate i in. Artykuł SODA 2007 Kompresowanie zdjęć prostoliniowych i minimalizowanie list kontroli dostępu. Udowadniają, że zminimalizowanie bardziej ogólnego wariantu powyższych reguł dopasowywania prefiksów jest trudne dla NP i połącz je (ponownie) z ładnymi zdjęciami prostokątów, aby rozwiązać problem!

Dziwię się, że nikt nie powiedział, że algorytm euklidesowy znajduje największy wspólny czynnik między dwiema liczbami. Możesz poradzić sobie z tym problemem, rysując prostokąt axb, a następnie podziel prostokąt na kwadrat utworzony przez najmniejszą stronę, powtórz dla pozostałego prostokąta, powtarzaj dla pozostałych prostokątów, aż znajdziesz kwadrat, który może równomiernie podzielić pozostały prostokąt (patrz animowany gif na stronie algorytmu euklidesowego).

Całkiem elegancki sposób na sprawdzenie, jak to działa, IMO.

Prawdopodobnie jest ich zbyt wiele, by je wymienić, ale jednym klasycznym przykładem (podkreślonym przez Aignera i Zieglera jako „ Dowód z książki ”) jest użycie przez Lovásza reprezentacji geometrycznej do rozwiązania problemu dotyczącego pojemności Shannona. Chociaż dowód został opublikowany w 1979 r. I rozwiązał otwarte pytanie z 1956 r., Pozostaje to najnowocześniejszy.

Związek kodów korekcji błędów z sieciami, pakowaniem kul itp. (Np. Książka Conwaya i Sloane'a). Jednak relacja jest tak silna, że ​​nie jest całkiem jasne, czy powinienem nazwać kody korekcji błędów „całkowicie nie geometrycznymi” ...

Techniki redukcji krat , takie jak LLL lub PSLQ , są wysoce geometryczne i rozwiązują problemy teorii liczb czystych, takie jak liniowe przybliżenie diofantyny i wykrywanie relacji liczb całkowitych.

$\mathbb{Z}$$\mathbb{Z}$

Gerard Salton wpadł na pomysł wykorzystania cosinusa kąta między wektorami (podobieństwo cosinusa) do systemów wyszukiwania informacji. Służyło to do obliczenia terminu częstotliwość-odwrotność częstotliwości dokumentów. Uważam to za poprzednika współczesnych wyszukiwarek. Zobacz także Model przestrzeni wektorowej.

$k$$k$

Oczywiście dowód jest bardziej topologiczny niż geometryczny, ale w niskim wymiarze ma wyraźny obraz geometryczny. Według mojej najlepszej wiedzy nie istnieje żaden dowód kombinatoryczny (tj. Dowód, który można wyjaśnić osobie, która nie chce słyszeć niczego o topologii).

Rola krzywych wypełniania przestrzeni w bazach danych i optymalizacji: http://people.csail.mit.edu/jaffer/Geometry/MDSFC

Obsługa maszyny wektorowej w uczeniu maszynowym prawdopodobnie się kwalifikuje.

Istnieją techniki obliczeniowej geometrii do rozwiązywania programowania liniowego. Geometria obliczeniowa: algorytmy i aplikacje zawierają ładny i prosty rozdział na ten temat.

Całka z funkcji może być przedstawiony jako zawartą powierzchni obszaru ograniczonego przez jego wykresie.