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

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

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

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

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

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