Robust geometric computation: Difference between revisions

Revision as of 22:14, 12 February 2014

Revision as of 22:20, 12 February 2014

Line 3:

(Extremely rough draft #1)

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.

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.

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

Geometric algorithms that operate on geometric objects are best thought of as

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.

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

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.

== 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

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.