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 -