On the computation of the topology of a non-reduced implicit space curve

ABSTRACT

An algorithm is presented for the computation of the topology of a non-reduced space curve defined as the intersection of two implicit algebraic surfaces.

It computes a Piecewise Linear Structure (PLS) isotopic to the original space curve.

The algorithm is designed to provide the exact result for all inputs. It's a symbolic-numeric algorithm based on subresultant computation. Simple algebraic criteria are given to certify the output of the algorithm.

The algorithm uses only one projection of the non-reduced space curve augmented with adjacency information around some "particular points" of the space curve.

The algorithm is implemented with the Mathemagix Computer Algebra System (CAS) using the SYNAPS library as a backend.

REFERENCES

• 1: Lionel Alberti , Bernard Mourrain, Visualisation of Implicit Algebraic Curves, Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, p.303-312, October 29-November 02, 2007 [doi>10.1109/PG.2007.66]
• 2: G. Alcazár, and J.R Sendra. Computation of the Topology of Algebraic Space Curves. J.Symbolic Comput., vol. 39, no. 6, 719--744, 2005.
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: Benedetti and J.J Risler. Realalgebraic and semi-algebraic sets, Actualités Mathématiques. {CurrentMathematical Topics}, Hermann, Paris, 1990.
• 5: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 6: Mhammed El Kahoui, Topology of real algebraic space curves, Journal of Symbolic Computation, v.43 n.4, p.235-258, April, 2008 [doi>10.1016/j.jsc.2007.10.008]
• 7: Stefan Arnborg , Huichun Feng, Algebraic decomposition of regular curves, Journal of Symbolic Computation, v.5 n.1-2, p.131-140, February/April 1988 [doi>10.1016/S0747-7171(88)80009-9]
• 8: Dennis S. Arnon , Scott McCallum, A polynomical-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, v.5 n.1-2, p.213-236, February/April 1988 [doi>10.1016/S0747-7171(88)80013-0]
• 9: M. Coste, Thoms's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, Journal of Symbolic Computation, v.5 n.1-2, p.121-129, February/April 1988 [doi>10.1016/S0747-7171(88)80008-7]
• 10: Sakkalis. The topological configuration of real algebraic curves. Bultin of the Australian Mathematical Society, 43: 37--50, 19.
• 11: Eisenbud. Commutative Algebra with a view toward Algebraic Geometry. vol. 150, Graduated Texts in Math., Berlin, Springer-Verlag, 1994.
• 12: Gatellier, A. Labrouzy, B. Mourrain, and J.P. Técourt. Computing the topology of three-dimensional algebraic curves. In Computational methods for algebraic spline surfaces, p. 27--43, Springer, Berlin, 2005.
• 13: Laureano Gonzalez-Vega , Ioana Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, v.19 n.9, p.719-743, December 2002 [doi>10.1016/S0167-8396(02)00167-X]
• 14: Thomas A. Grandine, Applications of Contouring, SIAM Review, v.42 n.2, p.297-316, June 2000 [doi>10.1137/S003614459936403X]
• 15: Thomas A. Grandine , Frederick W. Klein, IV, A new approach to the surface intersection problem, Computer Aided Geometric Design, v.14 n.2, p.111-134, Feb. 1997 [doi>10.1016/S0167-8396(96)00024-6]
• 16: B. Mourrain , M. N. Vrahatis , J. C. Yakoubsohn, On the complexity of isolating real roots and computing with certainty the topological degree, Journal of Complexity, v.18 n.2, p.612-640, June 2002 [doi>10.1006/jcom.2001.0636]
• 17: C. Owen, and A.P. Rockwood. Intersection of general implicit surfaces. In Geometric modeling, SIAM,335--345, 1987.
• 18: Arno Eigenwillig , Michael Kerber , Nicola Wolpert, Fast and exact geometric analysis of real algebraic plane curves, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277570]
• 19: Mittermaier, W. Schreiner and F. Winkler. Plotting Algebraic Space Curves by Cluter Computing. In Proc. of ASCM 2000.pp. 49--58 .
• 20: Hoon Hong, An efficient method for analyzing the topology of plane real algebraic curves, Mathematics and Computers in Simulation, v.42 n.4-6, p.571-582, Nov. 1996
• 21: C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
• 22: Keyser, T. Culver., D. Manocha, S. Krishnan Efficient and Exact Manipulation of Algebraic Points and Curves 2000 Comput. Aided. Geom. Design 32(11), 649--662.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Performance

Keywords:
algebraic curves, exact geometric computation, generic conditions, sturm-habicht sequence, subresultants sequence, topology computation