Надежные геометрические вычисления

В математике, особенно в вычислительной геометрии , геометрическая неробастность — это проблема, при которой решения о ветвлениях в алгоритмах вычислительной геометрии основаны на приближенных численных вычислениях, что приводит к различным формам ненадежности, включая неправильно сформированный вывод и сбой программного обеспечения из-за сбоя или бесконечных циклов.

Например, алгоритмы для решения таких задач, как построение выпуклой оболочки , основаны на проверке того, имеют ли определенные «числовые предикаты» положительные, отрицательные или нулевые значения. Если неточное вычисление с плавающей запятой приводит к тому, что значение, близкое к нулю, имеет знак, отличный от его точного значения, возникающие несоответствия могут распространиться по алгоритму, что приведет к тому, что он выдаст выходные данные, далекие от правильного вывода, или даже выйдет из строя.

Один из способов избежать этой проблемы включает использование целых чисел, а не чисел с плавающей запятой для всех координат и других величин, представленных алгоритмом, а также определение точности, необходимой для всех вычислений, чтобы избежать условий целочисленного переполнения . Например, двумерные выпуклые оболочки можно вычислить с использованием предикатов, проверяющих знак квадратичных многочленов , и, следовательно, для этих вычислений может потребоваться вдвое больше бит точности, чем для входных чисел. Когда целочисленная арифметика не может быть использована (например, когда результатом вычисления является алгебраическое число , а не целое или рациональное число), второй метод заключается в использовании символьной алгебры для выполнения всех вычислений с точно представленными алгебраическими числами, а не с числовыми приближениями. им. Третий метод, иногда называемый «фильтром с плавающей запятой», заключается в том, чтобы сначала вычислить числовые предикаты, используя неточный метод, основанный на арифметике с плавающей запятой , но сохранить границы точности результата и повторить расчет, используя более медленные методы символьной алгебры. или численно с дополнительной точностью, если эти границы не отделяют расчетное значение от нуля.

Ссылки

• Мэй, Банда; Типпер, Джон К.; Сюй, Ненгсюн (2014), «Численная устойчивость в геометрических вычислениях: пояснительное резюме», Applied Mathematics & Information Sciences , 8 (6): 2717–2727, doi : 10.12785/amis/080607 , MR   3228669 , S2CID   54807426
• Шарма, Викрам; Яп, Чи К. (2017), «Надежные геометрические вычисления» (PDF) , в Гудмане, Джейкоб Э .; О'Рурк, Джозеф ; Тот, Чаба Д. (ред.), Справочник по дискретной и вычислительной геометрии , Серия CRC Press по дискретной математике и ее приложениям (3-е изд.), CRC Press, стр. 1189–1223, MR   1730191
• Шевчук, Джонатан (15 апреля 2013 г.), Конспект лекций по геометрической устойчивости (PDF)