We address univariate root isolation when the polynomial’s coefficients are in a multiple field extension. We consider a polynomial F ∈ L[Y], where L is a multiple algebraic extension of . We provide aggregate bounds for F and algorithmic and bit-complexity results for the problem of isolating its roots.

Given a parametric polynomial curve γ:[a,b] →Rn, how can we sample a random point x ∈ im(γ) in such a way that it is distributed uniformly with respect to the arc-length? Unfortunately, we cannot sample exactly such a point---even assuming we can perform exact arithmetic operations. So we end up with the following question: how does the method we choose affect the quality of the approximate sample we obtain? In practice, there are many answers. However, in theory, there are still gaps in our understanding. In this paper, we address this question from the point of view of complexity theory, providing bounds in terms of the size of the desired error.

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rn. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization.