Computación geométrica robusta

En matemáticas, específicamente en geometría computacional , la falta de robustez geométrica es un problema en el que las decisiones de ramificación en los algoritmos de geometría computacional se basan en cálculos numéricos aproximados, lo que da lugar a diversas formas de falta de fiabilidad, incluyendo resultados mal formados y fallos de software por bloqueos o bucles infinitos.

Por ejemplo, los algoritmos para problemas como la construcción de una envoltura convexa se basan en comprobar si ciertos "predicados numéricos" tienen valores positivos, negativos o cero. Si un cálculo de punto flotante inexacto provoca que un valor cercano a cero tenga un signo diferente al de su valor exacto, las inconsistencias resultantes pueden propagarse por el algoritmo, lo que provoca que produzca un resultado muy alejado del correcto, o incluso que falle.

Un método para evitar este problema consiste en usar números enteros en lugar de números de coma flotante para todas las coordenadas y otras cantidades representadas por el algoritmo, y determinar la precisión requerida para todos los cálculos para evitar condiciones de desbordamiento de enteros . Por ejemplo, las envolventes convexas bidimensionales se pueden calcular usando predicados que prueban el signo de polinomios cuadráticos , y por lo tanto pueden requerir el doble de bits de precisión en estos cálculos que los números de entrada. Cuando no se puede usar aritmética de enteros (por ejemplo, cuando el resultado de un cálculo es un número algebraico en lugar de un número entero o racional), un segundo método es usar álgebra simbólica para realizar todos los cálculos con números algebraicos representados exactamente en lugar de aproximaciones numéricas de ellos. Un tercer método, a veces llamado "filtro de coma flotante", consiste en calcular primero predicados numéricos usando un método inexacto basado en aritmética de coma flotante , pero manteniendo límites en la precisión del resultado, y repetir el cálculo usando métodos de álgebra simbólica más lentos o numéricamente con precisión adicional cuando estos límites no separan el valor calculado de cero.

• Mei, Gang; Tipper, John C.; Xu, Nengxiong (2014), "Robustez numérica en computación geométrica: un resumen expositivo", Applied Mathematics & Information Sciences , 8 (6): 2717– 2727, doi : 10.12785/amis/080607 , MR 3228669 , S2CID 54807426  
• Sharma, Vikram; Yap, Chee K. (2017), "Cálculo geométrico robusto" (PDF) , en Goodman, Jacob E .; O'Rourke, Joseph ; Tóth, Csaba D. (eds.), Handbook of Discrete and Computational Geometry , CRC Press Series on Discrete Mathematics and its Applications (3.ª  ed.), CRC Press, pp. 1189–1223 , MR 1730191  
• Shewchuk, Jonathan (15 de abril de 2013), Apuntes de clase sobre robustez geométrica (PDF)