Robust geometric computation
This article may meet Wikipedia's criteria for speedy deletion as either a page in the draftspace, or a declined/unsubmitted userspace Articles for Creation page that has not been edited (excluding bot edits) in over six months. See CSD G13.
If this article does not meet the criteria for speedy deletion, please remove this notice. This draft was nominated by CptViraj on October 27, 2019. If you plan to improve this draft, simply and remove the It MAY qualify to be deleted per WP:CSD#G13 as the edit before that occurred on March 11, 2019 (6.34 years ago). {{Db-afc}}, {{Db-draft}}, or {{Db-g13}} code.Administrators: check links, talk, history (last), and logs before deletion. This page was last edited by CptViraj (contribs | logs) at 08:42, 27 October 2019 (UTC) (5 years ago) |
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.
Geometric algorithms that operate on geometric objects are best thought of as two types[1] 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[2]. In other words[2], these algorithms assume that the numerical data in geometric objects are exact values in that can be stored and retrieved in constant time, and that arithmetic involving these values is performed in constant time.
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.