.png){kind=icon}
.png){kind=icon}
Return
A condition number analysis of a line-surface intersection algorithm
.png){kind=icon}
OA
AI
DOI：10.1137/060668043.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose an algorithm based on Newton's method and subdivision for finding all zeros of a polynomial system in a bounded region of the plane. This algorithm can be used to find the intersections between a line and a surface, which has applications in graphics and computer-aided geometric design. The algorithm can operate on polynomials represented in any basis that satisfies a few conditions. The power basis, the Bernstein basis, and the first-kind Chebyshev basis are among those compatible with the algorithm. The main novelty of our algorithm is an analysis showing that its running is bounded only in terms of the condition number of the polynomial's zeros and a constant depending on the polynomial basis.
Keywords:
line/surface intersection
condition number analysis
hybrid algorithm
Newton's method
subdivision method
Journal
IF:
2.6
Papers:
5.1K
Citations:
1.8W