Condition Number Analyses of Line/Surface and Surface/Surface Intersection Algorithms
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.
computer science; numerical analysis; line/surface intersection; surface/surface intersection; condition number analysis; polynomial basis
Showing items related by title, author, creator and subject.
Alluvial Fan Surfaces In The Atacama Desert: Implications For Surface Modification Rates, The Earthquake Cycle, And Mars Baker, Amanda (2012-05-27)The Atacama Desert of Northern Chile is one of the oldest and driest landscapes on Earth. Many studies have referred to this landscape as relict, equating hyperaridity with abandonment as far as landscape modification is ...
Analytical Techniques To Optimize Trace Insecticide Detection Mechanisms Using Surface Plasmon Resonance And Surface-Enhanced Raman Spectroscopy Phifer, Adrienne (2013-05-26)This thesis uses Surface Plasmon Resonance (SPR) and Surface-Enhanced Raman Spectroscopy (SERS) to optimize trace insecticide detection mechanisms. Traditional methods for trace insecticide detection include Gas Chromatography ...