TY - GEN

T1 - Adaptive isotopic approximation of nonsingular curves

T2 - 25th Annual Symposium on Computational Geometry, SCG'09

AU - Lin, Long

AU - Yap, Chee

PY - 2009

Y1 - 2009

N2 - 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 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 Ro 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.

AB - 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 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 Ro 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.

KW - Curve approximation

KW - Exact numerical algorithms

KW - Isotopy

KW - Meshing

KW - Parametrizability

KW - Subdivision algorithms

KW - Topological correctness

UR - http://www.scopus.com/inward/record.url?scp=70849116923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70849116923&partnerID=8YFLogxK

U2 - 10.1145/1542362.1542423

DO - 10.1145/1542362.1542423

M3 - Conference contribution

AN - SCOPUS:70849116923

SN - 9781605585017

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 351

EP - 360

BT - Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09

Y2 - 8 June 2009 through 10 June 2009

ER -