Robust geometric computation: Difference between revisions

Revision as of 09:02, 12 February 2014

Revision as of 21:52, 12 February 2014

Line 22:

Geometric algorithms are typically designed and analyzed using the Real-RAM

model of computation \cite{preparata1977convex}. In other words, 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.

Geometric nonrobustness results from this unfortunate disconnect between

Line 48:

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

{{Reflist}}

De Berg, M., Van Kreveld, M., Overmars, M., & Schwarzkopf, O. C. (2000). Computational geometry. Computational Geometry, 1-17.

== External links ==