Solidne obliczenia geometryczne

W matematyce, szczególnie w geometrii obliczeniowej , niestabilność geometryczna jest problemem, w którym decyzje dotyczące rozgałęzień w algorytmach geometrii obliczeniowej są oparte na przybliżonych obliczeniach numerycznych, co prowadzi do różnych form zawodności, w tym źle sformułowanych danych wyjściowych i awarii oprogramowania w wyniku awarii lub nieskończonych pętli.

Na przykład algorytmy rozwiązywania problemów, takich jak konstrukcja wypukłej powłoki, polegają na sprawdzaniu, czy pewne „predykaty liczbowe” mają wartości dodatnie, ujemne lub zerowe. Jeśli niedokładne obliczenia zmiennoprzecinkowe powodują, że wartość bliska zeru ma inny znak niż jej dokładna wartość, wynikające z tego niespójności mogą rozprzestrzeniać się w algorytmie, powodując, że generuje on dane wyjściowe, które są dalekie od poprawnych danych wyjściowych, a nawet ulega awarii.

Jedna metoda uniknięcia tego problemu obejmuje użycie liczb całkowitych zamiast liczb zmiennoprzecinkowych dla wszystkich współrzędnych i innych wielkości reprezentowanych przez algorytm oraz określenie precyzji wymaganej dla wszystkich obliczeń w celu uniknięcia warunków przepełnienia liczb całkowitych . Na przykład dwuwymiarowe wypukłe kadłuby można obliczyć za pomocą predykatów, które sprawdzają znak wielomianów kwadratowych , a zatem mogą wymagać dwukrotnie większej liczby bitów precyzji w tych obliczeniach niż liczby wejściowe. Gdy nie można użyć arytmetyki liczb całkowitych (na przykład, gdy wynikiem obliczenia jest liczba algebraiczna zamiast liczby całkowitej lub wymiernej), drugą metodą jest użycie algebry symbolicznej do wykonywania wszystkich obliczeń z dokładnie przedstawionymi liczbami algebraicznymi, a nie numerycznymi przybliżeniami do nich. Trzecia metoda, czasami nazywana „filtrem zmiennoprzecinkowym”, polega na obliczeniu predykatów liczbowych najpierw przy użyciu niedokładnej metody opartej na arytmetyce zmiennoprzecinkowej , ale w celu utrzymania granic dokładności wyniku i powtórzenia obliczeń przy użyciu wolniejszych metod algebry symbolicznej lub numerycznie z dodatkową precyzją, gdy te granice nie oddzielają obliczonej wartości od zera.

•   Mei, Gang; Wywrotka, John C.; Xu, Nengxiong (2014), „Odporność numeryczna w obliczeniach geometrycznych: podsumowanie wykładu”, Applied Mathematics & Information Sciences , 8 (6): 2717–2727, doi : 10.12785 / amis / 080607 , MR 3228669
•   Sharma, Vikram; Yap, Chee K. (2017), „Solidne obliczenia geometryczne” (PDF) , w: Goodman, Jacob E .; O'Rourke, Józef ; Tóth, Csaba D. (red.), Handbook of Discrete and Computational Geometry , CRC Press Series on Discrete Mathematics and its Applications (wyd. 3), CRC Press, s. 1189–1223, MR 1730191
• Shewchuk, Jonathan (15 kwietnia 2013), Notatki z wykładu na temat wytrzymałości geometrycznej (PDF)