TY - GEN
T1 - Isotopic arrangement of simple curves
T2 - 4th International Congress on Mathematical Software, ICMS 2014
AU - Lien, Jyh Ming
AU - Sharma, Vikram
AU - Vegter, Gert
AU - Yap, Chee
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - We present a purely numerical (i.e., non-algebraic) subdivision algorithm for computing an isotopic approximation of a simple arrangement of curves. The arrangement is "simple" in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function on the plane, along with effective interval forms of the function and its partial derivatives. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A preliminary implementation is available in Core Library.
AB - We present a purely numerical (i.e., non-algebraic) subdivision algorithm for computing an isotopic approximation of a simple arrangement of curves. The arrangement is "simple" in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function on the plane, along with effective interval forms of the function and its partial derivatives. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A preliminary implementation is available in Core Library.
KW - Isotopy
KW - arrangement of curves
KW - interval arithmetic
KW - marching-cube
KW - subdivision algorithms
UR - http://www.scopus.com/inward/record.url?scp=84905845331&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84905845331&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-44199-2_43
DO - 10.1007/978-3-662-44199-2_43
M3 - Conference contribution
AN - SCOPUS:84905845331
SN - 9783662441985
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 277
EP - 282
BT - Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings
PB - Springer Verlag
Y2 - 5 August 2014 through 9 August 2014
ER -