On the exact computation of the topology of real algebraic curves. We consider the problem of computing a representation of the plane graph induced by one (or more) algebraic curves in the real plane. We make no assumptions about the curves, in particular we allow arbitrary singularities and arbitrary intersection. This problem has been well studied for the case of a single curve. All proposed approaches to this problem so far require finding and counting real roots of polynomials over an algebraic extension of Q, i.e. the coefficients of those polynomials are algebraic numbers. Various algebraic approaches for this real root finding and counting problem have been developed, but they tend to be costly unless speedups via floating point approximations are introduced, which without additional checks in some cases can render the approach incorrect for some inputs.par We propose a method that is always correct and that avoids finding and counting real roots of polynomials with non-rational coefficients. We achieve this using two simple geometric approaches: a triple projections method and a curve avoidance method. We have implemented our approach for the case of computing the topology of a single real algebraic curve. Even this prototypical implementation without optimizations appears to be competitive with other implementations.

References in zbMATH (referenced in 21 articles , 1 standard article )

Showing results 1 to 20 of 21.
Sorted by year (citations)

1 2 next

  1. Jin, Kai; Cheng, Jinsan: On the topology and isotopic meshing of plane algebraic curves (2020)
  2. Kaihnsa, Nidhi; Kummer, Mario; Plaumann, Daniel; Namin, Mahsa Sayyary; Sturmfels, Bernd: Sixty-four curves of degree six (2019)
  3. Imbach, Rémi; Moroz, Guillaume; Pouget, Marc: A certified numerical algorithm for the topology of resultant and discriminant curves (2017)
  4. Lazard, Sylvain; Pouget, Marc; Rouillier, Fabrice: Bivariate triangular decompositions in the presence of asymptotes (2017)
  5. Sorber, Laurent; Domanov, Ignat; Van Barel, Marc; De Lathauwer, Lieven: Exact line and plane search for tensor optimization (2016)
  6. Blažková, Eva; Šír, Zbyněk: Identifying and approximating monotonous segments of algebraic curves using support function representation (2014)
  7. Kalla, C.; Klein, C.: Computation of the topological type of a real Riemann surface (2014)
  8. Berberich, Eric; Emeliyanenko, Pavel; Kobel, Alexander; Sagraloff, Michael: Exact symbolic-numeric computation of planar algebraic curves (2013)
  9. Cheng, Jin-San; Jin, Kai; Lazard, Daniel: Certified rational parametric approximation of real algebraic space curves with local generic position method (2013)
  10. Corless, Robert M.; Diaz-Toca, Gema M.; Fioravanti, Mario; Gonzalez-Vega, Laureano; Rua, Ignacio F.; Shakoori, Azar: Computing the topology of a real algebraic plane curve whose defining equations are available only “by values” (2013)
  11. Alcázar, Juan Gerardo; Díaz-Toca, Gema María: On the shape of curves that are rational in polar coordinates (2012)
  12. Kerber, Michael; Sagraloff, Michael: A worst-case bound for topology computation of algebraic curves (2012)
  13. Shen, Li-Yong; Cheng, Jin-San; Jia, Xiaohong: Homeomorphic approximation of the intersection curve of two rational surfaces (2012)
  14. Lin, Long; Yap, Chee: Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach (2011)
  15. Alcázar, Juan Gerardo; Díaz-Toca, Gema María: Topology of 2D and 3D rational curves (2010)
  16. Berberich, Eric; Kerber, Michael; Sagraloff, Michael: An efficient algorithm for the stratification and triangulation of an algebraic surface (2010)
  17. Cheng, Jinsan; Lazard, Sylvain; Peñaranda, Luis; Pouget, Marc; Rouillier, Fabrice: On the topology of real algebraic plane curves (2010)
  18. Diochnos, Dimitrios I.; Emiris, Ioannis Z.; Tsigaridas, Elias P.: On the asymptotic and practical complexity of solving bivariate systems over the reals (2009)
  19. Caravantes, Jorge; Gonzalez-Vega, Laureano: Computing the topology of an arrangement of implicitly defined real algebraic plane curves (2008)
  20. El Kahoui, M’hammed: Topology of real algebraic space curves (2008)

1 2 next