Robust geometrisk beräkning

Inom matematik, särskilt inom beräkningsgeometri , är geometrisk icke-robusthet ett problem där förgreningsbeslut i beräkningsgeometrialgoritmer är baserade på ungefärliga numeriska beräkningar, vilket leder till olika former av opålitlighet inklusive dåligt format utdata och mjukvarufel genom kraschar eller oändliga slingor.

Algoritmer för problem som konstruktionen av ett konvext skrov är till exempel beroende av att testa om vissa "numeriska predikat" har värden som är positiva, negativa eller noll. Om en inexakt flyttalsberäkning gör att ett värde som är nära noll har ett annat tecken än dess exakta värde, kan de resulterande inkonsekvenserna fortplanta sig genom algoritmen och få den att producera utdata som är långt ifrån korrekt utdata, eller till och med krascha.

En metod för att undvika detta problem involverar att använda heltal snarare än flyttal för alla koordinater och andra kvantiteter som representeras av algoritmen, och bestämma den precision som krävs för alla beräkningar för att undvika heltalsöversvämningsförhållanden . Till exempel kan tvådimensionella konvexa skrov beräknas med hjälp av predikat som testar tecknet för kvadratiska polynom , och kan därför kräva dubbelt så många bitar av precision inom dessa beräkningar som ingångstalen. När heltalsaritmetik inte kan användas (till exempel när resultatet av en beräkning är ett algebraiskt tal snarare än ett heltal eller rationellt tal), är en andra metod att använda symbolisk algebra för att utföra alla beräkningar med exakt representerade algebraiska tal snarare än numeriska approximationer till dem. En tredje metod, ibland kallad "flyttalsfilter", är att beräkna numeriska predikat först med en inexakt metod baserad på flyttalsaritmetik, men att bibehålla gränserna för hur exakt resultatet är, och upprepa beräkningen med långsammare symboliska algebrametoder eller numeriskt med ytterligare precision när dessa gränser inte skiljer det beräknade värdet från noll.

•   Mei, Gang; Tipper, John C.; Xu, Nengxiong (2014), "Numerical robustness in geometric computation: an expository summary", Applied Mathematics & Information Sciences , 8 (6): 2717–2727, doi : 10.12785/amis/080607 , MR 3228669
•   Sharma, Vikram; Yap, Chee K. (2017), "Robust geometric computation" (PDF) , i Goodman, Jacob E. ; O'Rourke, Joseph ; Tóth, Csaba D. (red.), Handbook of Discrete and Computational Geometry , CRC Press Series on Discrete Mathematics and its Applications (3:e upplagan), CRC Press, s. 1189–1223, MR 1730191
• Shewchuk, Jonathan (15 april 2013), föreläsningsanteckningar om geometrisk robusthet (PDF)