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 -