Устойчивая реализация алгоритмов вычислительной геометрии

YouTube

Хорошо описанный в предположении абсолютной точности всех вычислений алгоритм в некоторых случаях перестает работать из-за накапливающейся погрешности вычислений с плавающей точкой. В то же время нельзя заменить вычисления с плавающей точкой рациональной арифметикой(когда каждое число представляется в виде рациональной дроби с длинным числителем и длинным знаменателем) из соображений производительности.

Существует несколько известных приемов эффективной организации точных вычислений. Об одном из этих приемов, фильтрованном вычислении предикатов, и пойдет речь в данном докладе.

Список ключевых тем для обсуждения:

— особенности арифметики с плавающей точкой;
— подсчет погрешности арифметических выражений;
— особенности организации интервальной арифметики (interval arithmetic);
— арифметика произвольной точности на числах с плавающей точкой (adaptive precision floating-point arithmetic).

Страница лекции на сайте Computer Science клуба