A Worst-case Bound for Topology Computation of Algebraic Curves

Details A Worst-case Bound for Topology Computation of Algebraic Curves A Worst-case Bound for Topology Computation of Algebraic Curves

2011-04-08

arxiv.org/abs/1104.1510v1

Computer Science

Symbolic Computation

Scientific paper

Computing the topology of an algebraic plane curve $\mathcal{C}$ means to compute a combinatorial graph that is isotopic to $\mathcal{C}$ and thus represents its topology in $\mathbb{R}^2$. We prove that, for a polynomial of degree $n$ with coefficients bounded by $2^\rho$, the topology of the induced curve can be computed with $\tilde{O}(n^8(n+\rho^2))$ bit operations deterministically, and with $\tilde{O}(n^8\rho^2)$ bit operations with a randomized algorithm in expectation. Our analysis improves previous best known complexity bounds by a factor of $n^2$. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and by the consequent amortized analysis of the critical fibers of the algebraic curve.

Affiliated with

Also associated with

No associations

Rating

A Worst-case Bound for Topology Computation of Algebraic Curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Worst-case Bound for Topology Computation of Algebraic Curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Worst-case Bound for Topology Computation of Algebraic Curves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354182