A worst-case bound for topology computation of algebraic curves
Topology of real algebraic varieties (14P25) Computational aspects of algebraic curves (14Q05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
The authors improve a previous efficiency bound on topology computation of plane algebraic curves. This improvement comes not from a novel general approach (they claim it is the same as [\textit{L. Gonzalez-Vega} and \textit{I. Necula}, ``Efficient topology determination of implicitly defined algebraic plane curves, Comput. Aided Geom. Des. 19, No. 9, 719--743 (2002; Zbl 1043.68105)]. Instead, it is derived from improvements in real root isolation [\textit{M. Sagraloff}, ``On the complexity of real root isolation, \url{arXiv:1011.0344}] and subsequent refinement [\textit{M. Kerber} and \textit{M. Sagraloff}, ``Root refinement for real polynomials, \url{arXiv:1004.1362}], plus the use of amortized analysis: the bound for the complexity of isolating all fiber polynomials is usually the same as the worst-case bound for a single fiber (the technique is extensively used in [\textit{M. Kerber}, Geometric algorithms for algebraic curves and surfaces. Ph.D. Thesis, Universität des Saarlandes, Germany (2009)] and [\textit{A. Eigenwillig, M. Kerber} and \textit{N. Wolpert}, ``Fast and exact geometric analysis of real algebraic plane curves, ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation (ISSAC 2007), Waterloo, ON, Canada, July 29--August 1, 2007. New York, NY: Association for Computing Machinery (ACM). 151--158 (2007; Zbl 1190.14062)] according to the authors).
- 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
- scientific article; zbMATH DE number 4183588
- \texttt{PTOPO}: computing the geometry and the topology of parametric curves
- 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
- 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?)
- 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
- A polynomial-time algorithm for the topological type of real algebraic curve - extended abstract
- A polynomial-time algorithm for the topological type of real algebraic curve
- Computing the topology of a bounded non algebraic curve in the plane
- 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
- An improved upper complexity bound for the topology computation of a real algebraic plane curve
- 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
- On the computation of the topology of plane curves
- 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
- 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
- Nearly optimal refinement of real roots of a univariate polynomial
- Improving the topology computation of an arrangement of cubics
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)
