Robust geometric computation: Difference between revisions

Revision as of 07:28, 29 April 2020

Revision as of 23:25, 2 May 2020

Line 1:

In mathematics, specifically in [[computational geometry]], '''geometric nonrobustness''' is a problem wherein branching decisions in geometric algorithms are predicated on approximate numerical computations, leading to various forms of unreliability including ill-formed output and software failure through crashing or infinite loops.<!-- the writing of the following content needs to be improved:

Geometric objects on a digital computer are composed of two types of data: numerical and combinatorial. Examples of numerical data include the Cartesian coordinates of a point in 3-space, the length of a line segment connecting two such points, or the angle between two such line segments. Examples of combinatorial information include grouping two points as an edge, grouping a collection of edges as a face, or grouping a collection of faces as a surface.

Line 6 ⟶ 7:

Geometric algorithms are typically designed and analyzed using the Real-RAM model of computation<ref name=":0"><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; line-height: 16.1200008392334px; background-color: rgb(255, 255, 255);">De Berg, M., Van Kreveld, M., Overmars, M., & Schwarzkopf, O. C. (2000). Computational geometry. </span>''Computational Geometry''<span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; line-height: 16.1200008392334px; background-color: rgb(255, 255, 255);">, 1–17.</span></ref>. In other words<ref name=":0" />, these algorithms assume that the numerical data in geometric objects are exact values in <math>\mathbb{R}</math> that can be stored and retrieved in constant time, and that arithmetic involving these values is performed in constant time.

Geometric nonrobustness results from this unfortunate disconnect between continuous theoretical formulations and the reality of discrete machine implementation. In most instances, the numerical data composing geometric objects is an approximation to a real value. Predicates that assume exact values but are fed approximate values are liable to make incorrect determinations. Constructions compound the situation by taking exact values and producing approximate ones, or by taking approximate values and producing even coarser approximations. In short, geometric nonrobustness is a problem wherein branching decisions in geometric algorithms are predicated on approximate numerical computations, leading to various forms of unreliability including ill-formed output and software failure through crashing or infinite loops.->

== References ==

* http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf<!--- Categories --->

{{geometry-stub}}

== References ==