= Computational geometry
<Computational geometry> designs and analyzes <algorithms> for geometric objects represented by coordinates or combinatorial structure. Problems include finding a <convex hull>, intersecting <line segments>[segments] and locating <points> in a subdivision. The representation and numerical predicates are part of correctness, not merely implementation details.
For <points> $p,q,r$ in the plane, the <orientation predicate> uses the sign of
$$
(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).
$$
A positive sign places $r$ to the left of the directed line from $p$ to $q$; zero means <collinearity>. The <points> $(0,0),(1,0),(0,1)$ give a positive <determinant>. Near-collinear inputs can make <round-off error> reverse the sign and corrupt an <algorithm>'s combinatorial decisions. Shewchuk's adaptive predicates increase arithmetic precision only as needed to certify the correct sign.<Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates by Jonathan Richard Shewchuk>[author's explanation of orientation tests and adaptive arithmetic]{ref}
Back to article page
