On the Geometry and the Topology of Parametric Curves

Abstract

We consider the problem of computing the topology and describing the geometry of a parametric curve in R-n. 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. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients tau, then the worst case bit complexity of PTOPO is (O) over tilde (B) (nd(6) + nd(5)tau + d(4) (n(2) + n tau) + d(3) (n(2)tau + n(3)) + n(3)d(2)tau). This bound matches the current record bound (O) over tilde (B)(d(6) +d(5)tau) for the problem of computing the topology of a planar algebraic curve given in implicit form. For planar and space curves, if N = max{d , tau}, the complexity of PTOPO becomes (O) over tilde (B)(N-6), which improves the state-of-the-art result, due to Alcazar and Diaz-Toca [CAGD'10], by a factor of N-10. However, visualizing the curve on top of the abstract graph construction, increases the bound to (O) over tilde (B) (N-7). We have implemented PTOPO in maple for the case of planar curves. Our experiments illustrate its practical nature.