Robust geometric computation: Difference between revisions

Revision as of 22:20, 12 February 2014

Latest revision as of 23:16, 12 May 2024

(30 intermediate revisions by 11 users not shown)

Line 1:

{{inline |date=May 2024}}

{{Userspace draft|source=ArticleWizard|date=February 2014}}

In mathematics, specifically in [[computational geometry]], '''geometric nonrobustness''' is a problem wherein branching decisions in [[computational geometry]] 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]] 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.

(Extremely rough draft #1)

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 integer arithmetic cannot be used (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.

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.

== References ==

Geometric algorithms that operate on geometric objects are best thought of as two types<ref><span style="color: rgb(34, 34, 34); font-family: Arial, sans-serif; line-height: 16.1200008392334px; background-color: rgb(255, 255, 255);">Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms.</span></ref> of operations: predicates and constructions. Predicates determine

*{{citation

relationships between objects. A predicate might determine if a point is to the left, right, or is collinear with a line segment, determine if a point is inside, outside, or on a circle, or determine if a line intersects a plane in one, none, or infinitely many points. Constructions produce new geometric objects from existing geometric objects. A construction might produce the rotation of a point around an origin, produce the point of intersection between two line segments, or produce an offset of an algebraic curve.

| 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

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

[[Category:Computational geometry]]

== Section 1 ==

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. From a practical point of view, it may seem like an odd or frustrating decision to assume access to infinite precision real arithmetic, given that digital computers are finite objects. From a theoretical point of view, this is a

sensible choice given that for subsets of <math>\mathbb{R}</math>, such as the rational

numbers <math>\mathbb{Q}</math>, many fundamental geometric axioms no longer hold.

== Section 2 ==

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.

== Section 3 ==

blah blah

== Section 4 ==

blah blah blah

== References ==

<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->

{{Reflist}}<references />

{{geometry-stub}}

== External links ==<!--- Categories --->

[[Category:Articles created via the Article Wizard]]