JavaScript is disabled for your browser. Some features of this site may not work without it.
Condition Number Analyses of Line/Surface and Surface/Surface Intersection Algorithms

Author
Srijuntongsiri, Gun
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.
Date Issued
2007-12-20Subject
computer science; numerical analysis; line/surface intersection; surface/surface intersection; condition number analysis; polynomial basis
Related items
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 ...