Table of Contents for Robust and Error-Free Geometric Computing

1   Introduction
    1.1 Eigendecomposition for 3x3 Symmetric Matrices
        1.1.1   Computing the Eigenvalues
        1.1.2   Computing the Eigenvectors
        1.1.3   A Nonrobust Floating-Point Implementation
        1.1.4   A Robust Floating-Point Implementation
       Computing the Eigenvalues
       Computing the Eigenvectors
        1.1.5   An Error-Free Implementation
    1.2 Distance between Line Segments
        1.2.1   Nonparallel Segments
        1.2.2   Parallel Segments
        1.2.3   A Nonrobust Floating-Point Implementation
        1.2.4   A Robust Floating-Point Implementation
       Conjugate Gradient Method
       Constrained Conjugate Gradient Method
        1.2.5   An Error-Free Implementation

2 Floating-Point Arithmetic
    2.1 Binary Encodings
    2.2 Binary Encoding of 32-bit Floating-Point Numbers
    2.3 Binary Encoding of 64-bit Floating-Point Numbers
    2.4 Rounding of Floating-Point Numbers
        2.4.1   Round to Nearest with Ties to Even
        2.4.2   Round to Nearest with Ties to Away
        2.4.3   Round Toward Zero
        2.4.4   Round Toward Positive 
        2.4.5   Round Toward Negative
        2.4.6   Rounding Support in C++

3 Arbitrary-Precision Arithmetic 
    3.1 Binary Scientific Notation
    3.2 Binary Scientific Numbers
        3.2.1   Addition
        3.2.2   Subtraction 
        3.2.3   Multiplication 
    3.3 Binary Scientific Rationals
        3.3.1   Addition and Subtraction
        3.3.2   Multiplication and Division
    3.4 Conversions
        3.4.1   Floating-Point Number to BSNumber
        3.4.2   BSNumber to Floating-Point Number
        3.4.3   BSRational to BSNumber of Specified Precision
        3.4.4   BSNumber to BSNumber of Specified Precision
    3.5 Performance Considerations
        3.5.1   Static Computation of Maximum Bits of Precision
       Addition and Subtraction
        3.5.2   Dynamic Computation of Maximum Bits of Precision
        3.5.3   Memory Management

4 Interval Arithmetic
    4.1 Arithmetic Operations
    4.2 Signs of Determinants
    4.3 Primal Queries
        4.3.1   Queries in 2D
        4.3.2   Queries in 3D

5 Quadratic-Field Arithmetic
    5.1 Sources of Rounding Errors
        5.1.1   Rounding Errors when Normalizing Vectors
        5.1.2   Errors in Roots to Quadratic Equations
        5.1.3   Intersection of Line and Cone Frustum
    5.2 Real Quadratic Fields
        5.2.1   Arithmetic Operations
        5.2.2   Allowing for Non-Square-Free d 
        5.2.3   Allowing for Rational d
    5.3 Comparisons of Quadratic Field Numbers
    5.4 Expressions with Multiple Square Roots
        5.4.1   Quadratic Fields with Multiple Square Roots
        5.4.2   Composition of Quadratic Fields
    5.5 Estimating a Quadratic Field Number
        5.5.1   Estimating a Rational Number
        5.5.2   Estimating the Square Root of a Rational Number
        5.5.3   Estimating a 1-Root Quadratic Field Number
        5.5.4   Estimating a 2-Root Quadratic Field Number
       Two Nonzero Radical Coefficients
       Three Nonzero Radical Coefficients

6 Numerical Methods 
    6.1 Root Finding
        6.1.1   Function Evaluation
        6.1.2   Bisection
        6.1.3   Newton's Method
        6.1.4   Hybrid Newton-Bisection Method
        6.1.5   Newton's Method and Arbitrary-Precision Arithmetic
    6.2 Polynomial Root Finding
        6.2.1   Discriminants
        6.2.2   Preprocessing the Polynomials
        6.2.3   Quadratic Polynomial
        6.2.4   Cubic Polynomial
       Nonsimple Real Roots
       One Simple Real Root
       Three Simple Real Roots
        6.2.5   Quartic Polynomial
       Processing the Root Zero
       The Biquadratic Cas
       Multiplicity Vector (3,1,0,0)
       Multiplicity Vector (2,2,0,0)
       Multiplicity Vector (2,1,1,0)
       Multiplicity Vector (1,1,1,1)
        6.2.6   High-Degree Polynomials
       Bounding Root Sequences by Derivatives
       Bounding Roots by Sturm Sequences
       Root Counting by Descartes' Rule of Signs
       Real-Root Isolation
    6.3 Linear Algebra
        6.3.1   Systems of Linear Equations
        6.3.2   Eigendecomposition for 2x2 Symmetric Matrices
        6.3.3   Eigendecomposition for 3x3 Symmetric Matrices
		6.3.4   3D Rotation Matrices with Rational Elements

7 Distance Queries
    7.1 Introduction
        7.1.1   The Quadratic Programming Problem
        7.1.2   The Linear Complementarity Problem
        7.1.3   The Convex Quadratic Programming Problem
       Eliminating Unconstrained Variables
       Reduction for Equality Constraints
    7.2 Lemke's Method
        7.2.1   Terms and Framework
        7.2.2   LCP with a Unique Solution
        7.2.3   LCP with Infinitely Many Solutions
        7.2.4   LCP with No Solution
        7.2.5   LCP with a Cycle
        7.2.6   Avoiding Cycles when Constant Terms are Zero
    7.3 Formulating a Geometric Query as a CQP
        7.3.1   Distance Between Oriented Boxes
        7.3.2   Test-Intersection of Triangle and Cylinder
    7.4 Implementation Details
        7.4.1   The LCP Solver
        7.4.2   Distance Between Oriented Boxes in 3D
        7.4.3   Test-Intersection of Triangle and Cylinder in 3D
        7.4.4   Accuracy Problems with Floating-Point Arithmetic
        7.4.5   Dealing with Vector Normalization

8 Intersection Queries
    8.1 Method of Separating Axes
        8.1.1   Separation by Projection onto a Line
        8.1.2   Separation of Convex Polygons in 2D
        8.1.3   Separation of Convex Polyhedra in 3D
        8.1.4   Separation of Convex Polygons in 3D
        8.1.5   Separation of Moving Convex Objects
        8.1.6   Contact Set for Moving Convex Objects
    8.2 Triangles Moving with Constant Linear Velocity
        8.2.1   Two Moving Triangles in 2D
        8.2.2   Two Moving Triangles in 3D
    8.3 Linear Component and Sphere
        8.3.1   Test-Intersection Queries
       Line and Sphere
       Ray and Sphere
       Segment and Sphere
        8.3.2   Find-Intersection Queries
       Line and Sphere
       Ray and Sphere
       Segment and Sphere
    8.4 Linear Component and Box
        8.4.1   Test-Intersection Queries
       Lines and Boxes
       Rays and Boxes
       Segments and Boxes
        8.4.2   Find-Intersection Queries
       Liang--Barsky Clipping
       Lines and Boxes
       Rays and Boxes
       Segments and Boxes
    8.5 Line and Cone
        8.5.1   Definition of Cones
        8.5.2   Practical Matters for Representing Infinity
        8.5.3   Definition of a Line, Ray and Segment
        8.5.4   Intersection with a Line
       Case c2 != 0
       Case c2 = 0 and c1 != 0 
       Case c2 = 0 and c1 = 0
        8.5.5   Clamping to the Cone Height Range
        8.5.6   Pseudocode for Error-Free Arithmetic
       Intersection of Intervals
       Line-Cone Query
        8.5.7   Intersection with a Ray
        8.5.8   Intersection with a Segment
        8.5.9   Implementation using Quadratic-Field Arithmetic
    8.6 Intersection of Ellipses
        8.6.1   Ellipse Representations
       The Standard Form for an Ellipse
       Conversion to a Quadratic Equation
        8.6.2   Test-Intersection Query for Ellipses
        8.6.3   Find-Intersection Query for Ellipses
       Case d4 != 0 and e(xbar) != 0
       Case d4 != 0 and e(xbar) = 0
       Case d4 = 0, d2 != 0, and e2 != 0
       Case d4 = 0, d2 != 0, and e2 = 0
       Case d4 = 0 and d2 = 0
    8.7 Intersection of Ellipsoids
        8.7.1   Ellipsoid Representations
       The Standard Form for an Ellipsoid
       Conversion to a Quadratic Equation
        8.7.2   Test-Intersection Query for Ellipsoids
        8.7.3   Find-Intersection Query for Ellipsoids
       Two Spheres
       Sphere-Ellipsoid: 3-Zero Center
       Sphere-Ellipsoid: 2-Zero Center
       Sphere-Ellipsoid: 1-Zero Center
       Sphere-Ellipsoid: No-Zero Center
       Reduction to a Sphere-Ellipsoid Query

9 Computational Geometry Algorithms
    9.1 Convex Hull of Points in 2D
        9.1.1   Incremental Construction
        9.1.2   Divide-and-Conquer Method
    9.2 Convex Hull of Points in 3D
        9.2.1   Incremental Construction
        9.2.2   Divide-and-Conquer Method
    9.3 Delaunay Triangulation
        9.3.1   Incremental Construction
       Inserting Points
       Linear Walks and Intrinsic Dimension
       The Insertion Step
        9.3.2   Construction by Convex Hull
    9.4 Minimum-Area Circle of Points
    9.5 Minimum-Volume Sphere of Points
    9.6 Minimum-Area Rectangle of Points
        9.6.1   The Exhaustive Search Algorithm
        9.6.2   The Rotating Calipers Algorithm
       Computing the Initial Rectangle
       Updating the Rectangle
       Distinct Supporting Vertices
       Duplicate Supporting Vertices
       Multiple Polygon Edges Attain Minimum Angle
       The General Update Step
        9.6.3   A Robust Implementation
       Avoiding Normalization
       Indirect Comparisons of Angles
       Updating the Support Information
       Conversion to a Floating-Point Rectangle
    9.7 Minimum-Volume Box of Points
        9.7.1   Processing Hull Faces
       Comparing Areas
       Comparing Volumes
       Comparing Angles
                9.7.2 Processing Hull Edges
                9.7.3 Conversion to a Floating-Point Box