کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
401481 | 675369 | 2012 | 22 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves](/preview/png/401481.png)
Given a real valued function f(X,Y)f(X,Y), a box region B0⊆R2B0⊆R2 and ε>0ε>0, we want to compute an εε-isotopic polygonal approximation to the restriction of the curve S=f−1(0)S=f−1(0)={p∈R2:f(p)=0}={p∈R2:f(p)=0} to B0B0. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga & Vegter gave a numerical subdivision algorithm that is exact when the curve SS is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of SS. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.
► We present a complete numerical algorithm to approximate real algebraic curves.
► We generalize Plantinga & Vegter’s curve approximation algorithm to general regions.
► The output is topologically correct even in the presence of singularities.
► Our algorithm is the first numerical algorithm with this correctness statement.
► We use interval arithmetic and theoretical algebraic bounds to ensure correctness.
Journal: Journal of Symbolic Computation - Volume 47, Issue 2, February 2012, Pages 131–152