Robust geometric computation: Difference between revisions

Revision as of 04:53, 3 May 2020

Latest revision as of 23:16, 12 May 2024

(12 intermediate revisions by 3 users not shown)

Line 1:

{{inline |date=May 2024}}

In mathematics, specifically in [[computational geometry]], '''geometric nonrobustness''' is a problem wherein branching decisions in [[computational geometry algorithm]]s algorithms are predicatedbased on approximate numerical computations, leading to various forms of unreliability including ill-formed output and software failure through crashing or infinite loops.

For instance, algorithms for problems like the construction of a [[convex hull]] rely on testing whether certain "numerical predicates" have values that are positive, negative, or zero. If an inexact floating-point computation causes a value that is near zero to have a different sign than its exact value, the resulting inconsistencies can propagate through the algorithm causing it to produce output that is far from the correct output, or even to crash.

One method for avoiding this problem involves using integers rather than floating point numbers for all coordinates and other quantities represented by the algorithm, and determining the precision required for all calculations to avoid [[integer overflow]] conditions. For instance, two-dimensional convex hulls can be computed using predicates that test the sign of [[quadratic polynomial]]s, and therefore may require twice as many bits of precision within these calculations as the input numbers. When thisinteger arithmetic cannot be practicedused (for instance, when the result of a calculation is an [[algebraic number]] rather than an integer or rational number), a second method is to use [[symbolic algebra]] to perform all computations with exactly represented algebraic numbers rather than numerical approximations to them. A third method, sometimes called a "floating point filter", is to compute numerical predicates first using an inexact method based on [[floating -point arithmetic]], but to maintain bounds on how accurate the result is, and repeat the calculation using slower symbolic algebra methods or numerically with additional precision when these bounds do not separate the calculated value from zero.

== References ==

*{{citation

* http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf

| last1 = Mei | first1 = Gang

| last2 = Tipper | first2 = John C.

| last3 = Xu | first3 = Nengxiong

| doi = 10.12785/amis/080607

| issue = 6

| journal = Applied Mathematics & Information Sciences

| mr = 3228669

| pages = 2717–2727

| title = Numerical robustness in geometric computation: an expository summary

| volume = 8

| year = 2014| s2cid = 54807426

}}

*{{citation

| last1 = Sharma | first1 = Vikram

| last2 = Yap | first2 = Chee K.

| editor1-last = Goodman | editor1-first = Jacob E. | editor1-link = Jacob E. Goodman

| editor2-last = O'Rourke | editor2-first = Joseph | editor2-link = Joseph O'Rourke (professor)

| editor3-last = Tóth | editor3-first = Csaba D.

| contribution = Robust geometric computation

| contribution-url = https://www.csun.edu/~ctoth/Handbook/chap45.pdf

| edition = 3rd

| mr = 1730191

| pages = 1189–1223

| publisher = CRC Press

| series = CRC Press Series on Discrete Mathematics and its Applications

| title = Handbook of Discrete and Computational Geometry

| year = 2017}}

*{{citation

| last = Shewchuk | first = Jonathan | author-link = Jonathan Shewchuk

| date = April 15, 2013

| title = Lecture Notes on Geometric Robustness

* | httpurl = https://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf}}

[[Category:Computational geometry]]

{{geometry-stub}}