Certified simultaneous isotopic approximation of curves via subdivision
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911967683280896 |
|---|---|
| author | Burr, Michael Byrd, Michael |
| author_facet | Burr, Michael Byrd, Michael |
| contents | We present a certified algorithm based on subdivision for computing an isotopic approximation to any number of curves in the plane. Our algorithm is based on the certified curve approximation algorithm of Plantinga and Vegter. The main challenge in this algorithm is to correctly and efficiently identify and isolate all intersections between the curves. To overcome this challenge, we introduce a new and simple test that guarantees the global correctness of our output. A main step in our algorithm for approximating any number of curves is to correctly approximate a pair of curves. In addition to developing the details of this special case, we provide complexity analyses for both the number of steps and the bit-complexity of this algorithm using both worst-case bounds as well as those based on continuous amortization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_04908 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Certified simultaneous isotopic approximation of curves via subdivision Burr, Michael Byrd, Michael Computational Geometry Symbolic Computation Algebraic Geometry 68W30, 13P15, 14Q05, 14Q20, 14Q30, 14P25 We present a certified algorithm based on subdivision for computing an isotopic approximation to any number of curves in the plane. Our algorithm is based on the certified curve approximation algorithm of Plantinga and Vegter. The main challenge in this algorithm is to correctly and efficiently identify and isolate all intersections between the curves. To overcome this challenge, we introduce a new and simple test that guarantees the global correctness of our output. A main step in our algorithm for approximating any number of curves is to correctly approximate a pair of curves. In addition to developing the details of this special case, we provide complexity analyses for both the number of steps and the bit-complexity of this algorithm using both worst-case bounds as well as those based on continuous amortization. |
| title | Certified simultaneous isotopic approximation of curves via subdivision |
| topic | Computational Geometry Symbolic Computation Algebraic Geometry 68W30, 13P15, 14Q05, 14Q20, 14Q30, 14P25 |
| url | https://arxiv.org/abs/2302.04908 |