Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves

Michael Burr, Sung Woo Choi, Benjamin Galehouse, Chee K. Yap

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

Abstract

Given a real function f(X, Y), a box regionB and ε 0, we want to compute an ε-isotopic polygonal approximation to the curve C: f(X, Y) = 0 within B. We focus on subdivision algorithms because of their adaptive complexity. Plantinga & Vegter (2004) gave a numerical subdivision algorithm that is exact when the curve C is non-singular. They used a computational model that relies only on function evaluation and interval arithmetic. We generalize their algorithm to any (possibly non-simply connected) region B that does not contain singularities of C. With this generalization as subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete numerical method to treat implicit algebraic curves with isolated singularities.

Original languageEnglish (US)
Title of host publicationISSAC'08
Subtitle of host publicationProceedings of the 21st International Symposium on Symbolic and Algebraic Computation 2008
Number of pages1
DOIs
StatePublished - 2008
Event21st Annual Meeting of the International Symposium on Symbolic Computation, ISSAC 2008 - Linz, Hagenberg, Austria
Duration: Jul 20 2008Jul 23 2008

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Other

Other21st Annual Meeting of the International Symposium on Symbolic Computation, ISSAC 2008
CountryAustria
CityLinz, Hagenberg
Period7/20/087/23/08

Keywords

  • Evaluation bound
  • Im
  • Meshing
  • Root bound
  • Singularity

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves'. Together they form a unique fingerprint.

  • Cite this

    Burr, M., Choi, S. W., Galehouse, B., & Yap, C. K. (2008). Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves. In ISSAC'08: Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation 2008 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). https://doi.org/10.1145/1390768.1390783