In mathematics, specifically in

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, geometric nonrobustness is a problem wherein branching decisions in

algorithms are based 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 In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

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 polynomials, and therefore may require twice as many bits of precision within these calculations as the input numbers. When integer arithmetic cannot be used (for instance, when the result of a calculation is an

algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...

rather than an integer or rational number), a second method is to use

symbolic algebra A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The d ...

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 In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...

, 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

* * * Computational geometry {{geometry-stub