Isotopic Arrangement of Simple Curves: An Exact Numerical Approach Based on Subdivision

DOI10.1007/978-3-662-44199-2_43MaRDI QIDQ2879135zbMATH OpenOpenAlexFDO

Authors Jyh-Ming Lien, Vikram Sharma, Gert Vegter, Chee K. Yap

Publication date 8 September 2014

Published in Mathematical Software – ICMS 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.00811

zbMATH Keywords

arrangement of curvesinterval arithmeticisotopymarching-cubesubdivision algorithms

Mathematics Subject Classification ID

Computational aspects of algebraic curves (14Q05) Geometric aspects of numerical algebraic geometry (14Q65) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: This paper presents the first purely numerical (i.e., non-algebraic) subdivision algorithm for the 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 $f:mathbb{R}^{2}ightarrowmathbb{R}^2$, and effective interval forms of $f,fracpartialfpartialx,fracpartialfpartialy$ are available. 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 version of this paper without the appendices appeared in Lien et al. (2014).

Recommendations

• Certified simultaneous isotopic approximation of pairs of curves via subdivision
• Complete subdivision algorithms, II
• A subdivision method for arrangement computation of semi-algebraic curves
• Isotopic equivalence by Bézier curve subdivision for application to high performance computing
• On the generation of curvilinear meshes through subdivision of isoparametric elements
• Isotopic meshing of a real algebraic space curve
• Subdivision of Bézier curves for ambient isotopy in molecular modeling
• Curvature of approximating curve subdivision schemes
• A subdivision scheme for Poisson curves and surfaces
• Subdivision methods for the topology of 2d and 3d implicit curves

Cited in

(11)

• Certified numerical algorithm for isolating the singularities of the plane projection of generic smooth space curves
• Certified numerical real root isolation for bivariate nonlinear systems
• AN APPROXIMATE ARRANGEMENT ALGORITHM FOR SEMI-ALGEBRAIC CURVES
• A subdivision method for arrangement computation of semi-algebraic curves
• Complete subdivision algorithms, II
• Adaptive isotopic approximation of nonsingular curves: the parametrizability and nonlocal isotopy approach
• Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach
• Certified simultaneous isotopic approximation of pairs of curves via subdivision
• An Algorithm for the Intersection Problem of Planar Parametric Curves
• Certified simultaneous isotopic approximation of algebraic curves via subdivision
• Topology guaranteed and error controlled curve tracing for parametric surface-surface intersection

Describes a project that uses

Uses Software

• core 2

This page was built for publication: Isotopic Arrangement of Simple Curves: An Exact Numerical Approach Based on Subdivision

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879135)