Resultant-Based Methods for Plane Curves Intersection Problems

  • Laurent Busé
  • Houssam Khalil
  • Bernard Mourrain
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3718)


We present an algorithm for solving polynomial equations, which uses generalized eigenvalues and eigenvectors of resultant matrices. We give special attention to the case of two bivariate polynomials and the Sylvester or Bezout resultant constructions. We propose a new method to treat multiple roots, detail its numerical aspects and describe experiments on tangential problems, which show the efficiency of the approach. An industrial application of the method is presented at the end of the paper. It consists in recovering cylinders from a large cloud of points and requires intensive resolution of polynomial equations.


Intersection Point Singular Value Decomposition Polynomial System Multiple Root Quotient Ring 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Chaperon, T.: A note on the construction of right circular cylinders through five 3d points. Technical report, Centre de Robotique, École des mines de Paris (January 2003)Google Scholar
  2. 2.
    Chaperon, T., Goulette, F., Laurgeau, C.: Extracting cylinders in full 3d data using a random sampling method and the gaussian image. In: Ertl, T., Girod, B., Greiner, G., Nieman, H., Seidel, H. (eds.) Vision, Modeling and Visualization (VMV 2001), Stuttgart (November 2001)Google Scholar
  3. 3.
    Corless, R., Gianni, P., Trager, B.: A reordered schur factorization method for zero-dimensional polynomial systems with multiple roots. In: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, pp. 133–140. ACM, New York (1997) (electronic)CrossRefGoogle Scholar
  4. 4.
    Corless, R.M., Gonzalez-Vega, L., Necula, I., Shakoori, A.: Topology determination of implicitly defined real algebraic plane curves. An. Univ. Timişoara Ser. Mat.-Inform. 41(Special issue), 83–96 (2003)zbMATHMathSciNetGoogle Scholar
  5. 5.
    Devillers, O., Mourrain, B., Preparata, F.P., Trebuchet, P.: Circular cylinders through four or five points in space. Discrete Comput. Geom. 29(1), 83–104 (2003)zbMATHMathSciNetGoogle Scholar
  6. 6.
    Dickenstein, A., Emiris, I. (eds.): Solving Polynomial Equations: Foundations, Algorithms, and Applications. Algorithms and Computation in Mathematics, vol. 14. Springer, Heidelberg (2005)zbMATHGoogle Scholar
  7. 7.
    Elkadi, M., Mourrain, B.: Symbolic-numeric tools for solving polynomial equations and applications. In: Dickenstein, A., Emiris, I. (eds.) Solving Polynomial Equations: Foundations, Algorithms, and Applications. Algorithms and Computation in Mathematics, vol. 14, pp. 125–168. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  8. 8.
    Fulton, W.: Introduction to intersection theory in algebraic geometry. CBMS Regional Conference Series in Mathematics, vol. 54. Published for the Conference Board of the Mathematical Sciences, Washington (1984)Google Scholar
  9. 9.
    Golub, G.H., Van Loan, C.F.: Matrix computations, 3rd edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1996)zbMATHGoogle Scholar
  10. 10.
    González-Vega, L., Necula, I.: Efficient topology determination of implicitly defined algebraic plane curves. Comput. Aided Geom. Design 19(9), 719–743 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Kravitsky, N.: Discriminant varieties and discriminant ideals for operator vessels in Banach space. Integral Equations Operator Theory 23(4), 441–458 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Lang, S.: Algebra, 3rd edn. Graduate Texts in Mathematics, vol. 211. Springer, New York (2002)zbMATHGoogle Scholar
  13. 13.
    Manocha, D., Demmel, J.: Algorithms for intersecting parametric and algebriac curves ii; multiple intersections. Computer vision, Graphics and image processing: Graphical models and image processing 57, 81–100 (1995)Google Scholar
  14. 14.
    Mourrain, B.: A new criterion for normal form algorithms. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) AAECC 1999. LNCS, vol. 1719, pp. 430–443. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  15. 15.
    Mourrain, B., Trebuchet, P.: Solving projective complete intersection faster. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St. Andrews), pp. 234–241. ACM, New York (2000) (electronic)CrossRefGoogle Scholar
  16. 16.
    Oishi, S.: Fast enclosure of matrix eigenvalues and singular values via rounding mode controlled computation. Linear Algebra Appl. 324(1-3), 133–146 (2001); Special issue on linear algebra in self-validating methodszbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    Van der Waerden, B.L.: Modern algebra, New-York, vol. II. Frederick Ungar Publishing Co. (1948)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Laurent Busé
    • 1
  • Houssam Khalil
    • 2
  • Bernard Mourrain
    • 1
  1. 1.INRIA, GalaadSophia AntipolisFrance
  2. 2.Laboratoire de Mathématiques Appliquées de LyonUCBL and CNRSVilleurbanneFrance

Personalised recommendations