On the topology of planar algebraic curves

ABSTRACT

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position.

Previous methods based on the cylindrical algebraic decomposition (CAD) use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Gröbner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. Our algorithm isolates critical points in boxes and computes a decomposition of the plane by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm demonstrates its efficiency, in particular on high-degree non-generic curves.

REFERENCES

• 1: L. Alberti , B. Mourrain , J. Wintz, Topology and arrangement computation of semi-algebraic planar curves, Computer Aided Geometric Design, v.25 n.8, p.631-651, November, 2008 [doi>10.1016/j.cagd.2008.06.009]
• 2: 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]
• 3: Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
• 4: 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
• 5: R. Benedetti and J. Risler. Real Algebraic and Semi-algebraic Sets, Actualites Mathematiques. Hermann, 1990.
• 6: Christopher W. Brown, Improved projection for cylindrical algebraic decomposition, Journal of Symbolic Computation, v.32 n.5, p.447-465, November 2001 [doi>10.1006/jsco.2001.0463]
• 7: C. W. Brown. Contructing cylindrical algebraic decomposition of the plane quickly, 2002. Manuscript, http://www.cs.usna.edu/wcbrown/.
• 8: Christoph Burnikel , Stefan Funke , Kurt Mehlhorn , Stefan Schirra , Susanne Schmitt, A Separation Bound for Real Algebraic Expressions, Proceedings of the 9th Annual European Symposium on Algorithms, p.254-265, August 28-31, 2001
• 9: Michael Burr , Sung Woo Choi , Benjamin Galehouse , Chee K. Yap, Complete subdivision algorithms, II: isotopic meshing of singular algebraic curves, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria [doi>10.1145/1390768.1390783]
• 10: CGAL: Computational Geometry Algorithms Library. http://www.cgal.org.
• 11: 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]
• 12: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Number 185 in Graduate Texts in Mathematics. Springer, New York, 2nd edition, 2005.
• 13: Dimitrios I. Diochnos , Ioannis Z. Emiris , Elias P. Tsigaridas, On the complexity of real solving bivariate systems, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277567]
• 14: 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]
• 15: A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, and N. Wolpert. A Descartes Algorithm for Polynomials with Bit--Stream Coefficients. In V. Ganzha, E. Mayr, and E. Vorozhtsov, editors, CASC, volume 3718 of LNCS, pages 138--149. Springer, 2005.
• 16: Arno Eigenwillig , Vikram Sharma , Chee K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145786]
• 17: Arno Eigenwillig , Michael Kerber, Exact and efficient 2D-arrangements of arbitrary algebraic curves, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.122-131, January 20-22, 2008, San Francisco, California
• 18: Ioannis Z. Emiris , Bernard Mourrain , Elias P. Tsigaridas, Real Algebraic Numbers: Complexity Analysis and Experimentation, Reliable Implementation of Real Number Algorithms: Theory and Practice: International Seminar Dagstuhl Castle, Germany, January 8-13, 2006 Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-85521-7_4]
• 19: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 20: H. Feng. Decomposition and Computation of the Topology of Plane Real Algebraic Curves. Ph.d. thesis, The Royal Institute of Technology, Stockholm, 1992.
• 21: FGb -- A software for computing Gröbner bases. J.-C. Faugère. http://fgbrs.lip6.fr.
• 22: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 23: Laureano González-Vega , M'Hammed El Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, v.12 n.4, p.527-544, Dec. 1996 [doi>10.1006/jcom.1996.0032]
• 24: L. Gonzalez , H. Lombardi , T. Recio , M.-F. Roy, Sturm-Habicht sequence, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.136-146, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74558]
• 25: 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]
• 26: Gert-Martin Greuel , Gerhard Pfister , Hans Schönemann, SINGULAR — A computer algebra system for polynomial computations, Symbolic computation and automated reasoning, A. K. Peters, Ltd., Natick, MA, 2001
• 27: 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
• 28: M. Kerber. Analysis of real algebraic plane curves. Master's thesis, MPII, 2006.
• 29: J. Keyser, K. Ouchi, and M. Rojas. The exact rational univariate representation for detecting degeneracies. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS Press, 2005.
• 30: O. Labs. A list of challenges for real algebraic plane curve visualization software. Manuscript, 2008.
• 31: C. Li, S. Pion, and C. Yap. Recent progress in exact geometric computation. J. of Logic and Algebraic Programming, 64(1):85--111, 2004. Special issue on "Practical Development of Exact Real Number Computation".
• 32: Scott McCallum , George E. Collins, Local box adjacency algorithms for cylindrical algebraic decompositions, Journal of Symbolic Computation, v.33 n.3, p.321-342, March 2002 [doi>10.1006/jsco.2001.0499]
• 33: B. Mourrain, S. Pion, S. Schmitt, J.-P. Técourt, E. P. Tsigaridas, and N. Wolpert. Algebraic issues in Computational Geometry. In J.-D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, Mathematics and Visualization, chapter 3. Springer, 2006.
• 34: Bernard Mourrain , Philippe Trebuchet, Generalized normal forms and polynomial system solving, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.253-260, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073920]
• 35: F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. J. of Applicable Algebra in Engineering, Communication and Computing, 9(5):433--461, 1999.
• 36: Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004 [doi>10.1016/j.cam.2003.08.015]
• 37: RS -- A software for real solving of algebraic systems. F. Rouillier. http://fgbrs.lip6.fr.
• 38: T. Sakkalis. The topological configuration of a real algebraic curve. Bull. Austrl. Math. Soc., 43:37--50, 1991.
• 39: Takis Sakkalis , R. Farouki, Singular points of algebraic curves, Journal of Symbolic Computation, v.9 n.4, p.405-421, April 1990 [doi>10.1016/S0747-7171(08)80019-3]
• 40: Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]
• 41: A. Strzebonski. Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput., 41(9):1021--1038, 2006.
• 42: B. Teissier. Cycles évanescents, sections planes et conditions de Whitney. (french). In Singularités à Cargèse (Rencontre Singularités Géom. Anal., Inst. Études Sci., Cargèse, 1972), number 7--8 in Asterisque, pages 285--362. Soc. Math. France, Paris, 1973.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Experimentation

Keywords:
effective algebraic geometry, exact geometric computation, topology of algebraic curves