Robust geometric computation: Difference between revisions

Revision as of 21:52, 12 February 2014

Revision as of 22:01, 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

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 18 ⟶ 14:

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.

between two line segments, or produce an offset of an algebraic curve.

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