Isotopic arrangement of simple curves: An exact numerical approach based on subdivision

Jyh Ming Lien, Vikram Sharma, Gert Vegter, Chee Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationMathematical Software, ICMS 2014 - 4th International Congress, Proceedings
PublisherSpringer Verlag
Pages277-282
Number of pages6
ISBN (Print)9783662441985
DOIs
StatePublished - 2014
Event4th International Congress on Mathematical Software, ICMS 2014 - Seoul, Korea, Republic of
Duration: Aug 5 2014Aug 9 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8592 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Congress on Mathematical Software, ICMS 2014
CountryKorea, Republic of
CitySeoul
Period8/5/148/9/14

Keywords

  • Isotopy
  • arrangement of curves
  • interval arithmetic
  • marching-cube
  • subdivision algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Isotopic arrangement of simple curves: An exact numerical approach based on subdivision'. Together they form a unique fingerprint.

Cite this