A worst-case bound for topology computation of algebraic curves

DOI10.1016/j.jsc.2011.11.001zbMath1244.14048MaRDI 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 curve; complexity analysis; topology computation; amortized analysis

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

14Q05: Computational aspects of algebraic curves

14Q20: Effectivity, complexity and computational aspects of algebraic geometry

14P25: Topology of real algebraic varieties

Related Items

Algorithm for Connectivity Queries on Real Algebraic Curves, On Isolating Roots in a Multiple Field Extension, On the Topology of the Intersection Curve of Two Real Parameterized Algebraic Surfaces, Improved bounds for the CF algorithm, 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, Nearly optimal refinement of real roots of a univariate polynomial, Bounds for polynomials on algebraic numbers and application to curve topology, 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, On the Davenport-Mahler bound, 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, On the complexity of computing the topology of real algebraic space curves

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