A worst-case bound for topology computation of algebraic curves

DOI10.1016/J.JSC.2011.11.001MaRDI QIDQ765857zbMATH OpenOpenAlexFDO

Authors 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) Topology of real algebraic varieties (14P25) 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)

Recommendations

• An efficient method for analyzing the topology of plane real algebraic curves.
• Bounds for polynomials on algebraic numbers and application to curve topology
• Algorithm for Connectivity Queries on Real Algebraic Curves
• scientific article; zbMATH DE number 16645
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• On the complexity of computing with planar algebraic curves
• On the exact computation of the topology of real algebraic curves
• Publication:5749405
• \texttt{PTOPO}: computing the geometry and the topology of parametric curves

Cites work

• scientific article; zbMATH DE number 1253989 (Why is no real title available?)
• scientific article; zbMATH DE number 1157650 (Why is no real title available?)
• scientific article; zbMATH DE number 1157660 (Why is no real title available?)
• scientific article; zbMATH DE number 1446863 (Why is no real title available?)
• A generic algebraic kernel for non-linear geometric applications
• A polynomial-time algorithm for the topological type of real algebraic curve
• Algorithms in real algebraic geometry
• An efficient algorithm for the stratification and triangulation of an algebraic surface
• An efficient method for analyzing the topology of plane real algebraic curves.
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Arrangement computation for planar algebraic curves
• Complete subdivision algorithms, II
• Efficient real root approximation
• Efficient topology determination of implicitly defined algebraic plane curves.
• Fast and exact geometric analysis of real algebraic plane curves
• Modern computer algebra
• On nearest-neighbor graphs
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On the exact computation of the topology of real algebraic curves
• On the topology of planar algebraic curves
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993

Cited in

(21)

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

Describes a project that uses

Uses Software

• insulate

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

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