Condition Number Analyses of Line/Surface and Surface/Surface Intersection Algorithms

Abstract

Intersection problems have many applications in computational geometry and geometric modeling and design. This dissertation addresses two specific intersection problems: finding all intersections between a line and a parametric surface and between two parametric surfaces. New algorithms based on Newton's method and subdivision are proposed to solve these problems. Our algorithms also use a test based on the Kantorovich theorem to prevent the divergence or slow convergence issues normally associated with using unsuitable starting points for Newton's method. The algorithm for line/surface problem in particular can operate on polynomials represented in any basis that satisfies a few conditions. The power basis, Bernstein, and first-kind Chebyshev bases are among those compatible with the algorithm. The novelty of our algorithms is the analyses showing that their running time is bounded only in terms of the condition number of the problem instance and, in the line/surface case, the constant depending on the polynomial basis. This constant measures the tightness of the bounding polytope as compared to the bounded subsurface, which translates to the efficiency of the algorithm when the basis is used. The constant is different for each basis as each one lends itself to computation of different bounding polytope. We derive this constant for the three mentioned commonly used bases.