Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves |
| |
Authors: | Michael Burr Sung Woo Choi Chee K Yap |
| |
Affiliation: | a Courant Institute, NYU, 251 Mercer Street, New York, NY 10012, United Statesb Department of Mathematics, Duksung Women’s University, Seoul 132-714, Republic of Koreac Korea Institute of Advanced Study, 85 Hoegiro (Cheongnyangni-dong 207-43), Dongdaemun-gu, Seoul 130-722, Republic of Korea |
| |
Abstract: | Given a real valued function f(X,Y), a box region B0⊆R2 and ε>0, we want to compute an ε-isotopic polygonal approximation to the restriction of the curve S=f−1(0)={p∈R2:f(p)=0} to B0. 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 S 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 S. 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. |
| |
Keywords: | Meshing Singularity Root bound Evaluation bound Implicit algebraic curve Complete numerical algorithm Subdivision algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|