Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach (Q540445)

The paper describes algorithms that will find a piecewise linear approximation to a plane curve \(S\), characterized implicitly by \(f(x,y)=0\) within a given region \(R_0\subset{\mathbb R}^2\). The approximant is obtained by (dyadic) subdivision and it should be isotopic to \(S\) (topologically correct) and geometrically accurate (the distance to \(S\) should not be larger than \(\epsilon\)). First an isotopic approximant is constructed (isolation stage), which is then refined to attain the geometric accuracy (refinement stage). Three variants (with increasing complexity) for the algorithm of the isolation stage are proposed that are inspired by the methods that are described by \textit{S.~Plantinga} and \textit{G.~Vegter} [Isotopic approximation of implicit curves and surfaces, SGP~'04 Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 245--254, (1985)] (introducing nonlocal isotopy) and \textit{J. M.~Snyder} [``Interval analysis for computer graphics,'' ACM SIGGRAPH Computer Graphics Volume 26 Issue 2, 121--130, July 1992. Boston etc.: Academic Press, Inc. (1992; Zbl 0759.68089)] (introducing parametrizability). These ideas are first developed for a mesh of squares with quad-tree subdivision but the ideas are then generalized to rectangles (with bounded but variable aspect ratios) which nakes subdivision into half rectangles possible. Also the inition region \(R_0\) need not be square or rectangle but can be arbitrary, possibly not even connected. The dyadic subdivision allows for exact arithmetic (avoiding rounding error analysis). A proof for the topological correctness and that the termination of the algorithm after a finite number of steps is given under mild conditions. Numerical examples illustrate the method. The paper is very well structured and easily accessible.