Adaptive isotopic approximation of nonsingular curves: The parametrizability and nonlocal isotopy approach

We consider domain subdivision algorithms for computing isotopic approximations of nonsingular curves represented implicitly by an equation f (X, Y) = 0. Two algorithms in this area are from Snyder (1992) and Plantinga & Veg- ter (2004). We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parametrizability criterion for subdivision, and like Plantinga & Vegter we exploit non-local isotopy. We further extend our algorithm in two important and practical directions: first, we allow subdivision cells to be rectangles with arbitrary but bounded aspect ratios. Second, we extend the input domains to be regions R₀ with arbitrary geometry and which might not be simply connected. Our algorithm halts as long as the curve has no singularities in the region, and intersects the boundary of R_o transversally. Our algorithm is also easy to implement exactly. We report on very encouraging preliminary experimental results, showing that our algorithms can be much more efficient than both Plantinga & Vegter's and Snyder's algorithms.