A worst case bound for topology computation of algebraic curves
Kerber, Michael
Sagraloff, Michael
Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.
Elsevier
2012
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/3331
Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic curves. <i> Journal of Symbolic Computation</i>. 2012;47(3):239-258. doi:<a href="https://doi.org/10.1016/j.jsc.2011.11.001">10.1016/j.jsc.2011.11.001</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jsc.2011.11.001
info:eu-repo/semantics/openAccess