Adaptive Isotopic Approximation of Nonsingular Curves: The Parameterizability and Nonlocal Isotopy Approach

Long Lin, Chee Yap

Research output: Contribution to journalArticlepeer-review


We consider domain subdivision algorithms for computing isotopic approximations of a nonsingular algebraic curve. The curve is given by a polynomial equation f(X, Y)= 0. Two algorithms in this area are from Snyder (1992) SIGGRAPH Comput. Graphics, 26(2), 121 and Plantinga and Vegter (2004) In Proc. Eurographics Symposium on Geometry Processing, pp. 245-254. We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parameterizability criterion for subdivision, and like Plantinga and Vegter, we exploit nonlocal 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 R0 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 R0 transversally. Our algorithm is practical and easy to implement exactly. We report some very encouraging experimental results, showing that our algorithms can be much more efficient than the algorithms of Plantinga-Vegter and Snyder.

Original languageEnglish (US)
Pages (from-to)760-795
Number of pages36
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Jun 2011


  • Curve approximation
  • Exact algorithms
  • Isotopy
  • Meshing
  • Parameterizability
  • Subdivision algorithms
  • Topological correctness

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Adaptive Isotopic Approximation of Nonsingular Curves: The Parameterizability and Nonlocal Isotopy Approach'. Together they form a unique fingerprint.

Cite this