A worst-case bound for topology computation of algebraic curves

DOI10.1016/j.jsc.2011.11.001zbMath1244.14048OpenAlexW2059173068MaRDI QIDQ765857

Michael Kerber, Michael Sagraloff

Publication date: 22 March 2012

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2011.11.001

zbMATH Keywords

algebraic curvecomplexity analysistopology computationamortized analysis

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational aspects of algebraic curves (14Q05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Topology of real algebraic varieties (14P25)

Related Items (16)

On the Davenport-Mahler bound ⋮ On the complexity of computing the topology of real algebraic space curves ⋮ Improved bounds for the CF algorithm ⋮ Algorithm for Connectivity Queries on Real Algebraic Curves ⋮ On Isolating Roots in a Multiple Field Extension ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ On the Topology of the Intersection Curve of Two Real Parameterized Algebraic Surfaces ⋮ Certified rational parametric approximation of real algebraic space curves with local generic position method ⋮ On the complexity of the Descartes method when using approximate arithmetic ⋮ Separating linear forms and rational univariate representations of bivariate systems ⋮ A generic position based method for real root isolation of zero-dimensional polynomial systems ⋮ Root refinement for real polynomials using quadratic interval refinement ⋮ From approximate factorization to root isolation with application to cylindrical algebraic decomposition ⋮ Detecting similarity of rational plane curves ⋮ On the complexity of computing with planar algebraic curves ⋮ Bounds for polynomials on algebraic numbers and application to curve topology

Uses Software

• insulate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• An efficient algorithm for the stratification and triangulation of an algebraic surface
• A polynomial-time algorithm for the topological type of real algebraic curve
• On nearest-neighbor graphs
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
• An efficient method for analyzing the topology of plane real algebraic curves.
• Efficient topology determination of implicitly defined algebraic plane curves.
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Arrangement computation for planar algebraic curves
• Efficient real root approximation
• Complete subdivision algorithms, II
• On the exact computation of the topology of real algebraic curves
• On the topology of planar algebraic curves
• A generic algebraic kernel for non-linear geometric applications
• Algorithms in real algebraic geometry

This page was built for publication: A worst-case bound for topology computation of algebraic curves