Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach
type: Item
instance of: scholarly article
title: Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach
zbMATH Open document ID: 1221.65048
author: Long Lin
author: Chee K. Yap
published in: Discrete \& Computational Geometry
publication date: 2011-06-03T00:00:00Z
review text: 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.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65D17
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65G40
zbMATH DE Number: 5903704
zbMATH Keywords: meshing
zbMATH Keywords: curve approximation
zbMATH Keywords: isotopy
zbMATH Keywords: parameterizability
zbMATH Keywords: subdivision algorithm
zbMATH Keywords: topological correctness
zbMATH Keywords: exact algorithm
zbMATH Keywords: interval analysis
zbMATH Keywords: computer graphics
zbMATH Keywords: numerical examples
describes a project that uses: insulate
MaRDI profile type: Publication
full work available at URL: s00454-011-9345-9
OpenAlex ID: W4244574515
cites work: Algorithms in real algebraic geometry
cites work: Q5292193
cites work: Isotopic implicit surface meshing
cites work: Provably good sampling and meshing of surfaces
cites work: Complete subdivision algorithms, II
cites work: Complete numerical isolation of real roots in zero-dimensional triangular systems
cites work: Sampling and meshing a surface with guaranteed topology and geometry
cites work: Complete, exact, and efficient computations with cubic curves
cites work: An efficient method for analyzing the topology of plane real algebraic curves.
cites work: Comparison of interval methods for plotting algebraic curves
cites work: Q5566070
cites work: Q3992847
cites work: Q3707258
cites work: An exact and efficient approach for computing a cell in an arrangement of quadrics
cites work: On the exact computation of the topology of real algebraic curves
cites work: Complexity of real root isolation using continued fractions
cites work: Q4000448
cites work: Q3601542
cites work: Foundations of Exact Rounding
DOI: 10.1007/S00454-011-9345-9
description: scientific article; zbMATH DE number 5903704