Content deleted Content added
No edit summary |
No edit summary |
||
Line 11:
faces as a surface.
Geometric algorithms that operate on geometric objects are best thought of as
two types of operations: predicates and constructions. Predicates determine
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.
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 $\mathbb{R}$ 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 $\mathbb{R}$, such as the rational
numbers $\mathbb{Q}$, many fundamental geometric axioms no longer hold.
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 ==
| |||