A Condition Number Analysis of a Line-Surface Intersection Algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917022350180352 |
|---|---|
| author | Srijuntongsiri, Gun Vavasis, Stephen A. |
| author_facet | Srijuntongsiri, Gun Vavasis, Stephen A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0608090 |
| institution | arXiv |
| publishDate | 2006 |
| record_format | arxiv |
| spellingShingle | A Condition Number Analysis of a Line-Surface Intersection Algorithm Srijuntongsiri, Gun Vavasis, Stephen A. Numerical Analysis Computational Geometry 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. |
| title | A Condition Number Analysis of a Line-Surface Intersection Algorithm |
| topic | Numerical Analysis Computational Geometry |
| url | https://arxiv.org/abs/cs/0608090 |