Skip to main content

Advertisement

Springer Nature Link
Log in

CAD and Topology of Semi-Algebraic Sets

  • Published:
Mathematics in Computer Science Aims and scope Submit manuscript

Abstract

Although Cylindrical Algebraic Decomposition (CAD) is widely used to study the topology of semi-algebraic sets (especially algebraic curves), there are very few studies of the topological properties of the output of the CAD algorithms. In this paper three possible bad topological properties of the output of CAD algorithms are described. It is shown that these properties may not occur after a generic change of coordinates and that they may be avoided, in dimension not greater than three, with a modification of the CAD algorithm. As this modification of the CAD algorithm requires to solve some polynomial systems, it is also shown that the computation with real algebraic numbers may be advantageously replaced, in all the variants of the CAD algorithm, by solving systems of polynomial equations and inequalities.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Arnon, D.: A cellular decomposition algorithm for semialgebraic sets. In: Symbolic and Algebraic Computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979). Lecture Notes in Computer Science, vol. 72, pp. 301–315. Springer, Berlin (1979)

  2. Aubry P., Lazard D., Moreno-Maza M.: On the theories of triangular sets. Polynomial elimination—algorithms and applications (special issue). J. Symb. Comput. 28(1–2), 105–124 (1999)

    MATH  MathSciNet  Google Scholar 

  3. Basu, S.: Algorithmic semi-algebraic geometry and topology—recent progress and open problems. In: Surveys on Discrete and Computational Geometry. Contemp. Math., vol. 453, pp. 139–212. American Mathematical Society, Providence (2008)

  4. Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry, 2nd edn. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006)

  5. Bochnak, J., Coste, M., Roy, M.-F.: Real algebraic geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 36 [Results in Mathematics and Related Areas (3)]. Springer, Berlin (1998). Translated from the 1987 French original, Revised by the authors

  6. Boulier, F., Chen, C., Lemaire, F., Moreno-Maza, M.: Real root isolation of regular chains. In: The Joint Conference of ASCM 2009 and MACIS 2009, pp. 15–29, Kyushu University, Fukuoka, Japan (2009)

  7. Brown C.W.: Improved projection for cylindrical algebraic decomposition. J. Symb. Comput. 32(5), 447–465 (2001)

    Article  MATH  Google Scholar 

  8. Brown, C.W., Davenport, J.H.: The complexity of quantifier elimination and cylindrical algebraic decomposition. In: ISSAC’07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp. 54–60. ACM, New York (2007)

  9. Brown, C.W., McCallum, S.: On using bi-equational constraints in CAD construction. In: ISSAC’05, pp. 76–83 (electronic). ACM, New York (2005)

  10. Chen, C., Moreno-Maza, M., Xia, B., Yang, L.: Computing cylindrical algebraic decomposition via triangular decomposition. In: ISSAC ’09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, pp. 95–102. ACM, New York (2009)

  11. Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Automata Theory and Formal Languages (Second GI Conf., Kaiserslautern, 1975), pp. 134–183. Lecture Notes in Computer Science, vol. 33. Springer, Berlin (1975)

  12. Faugère J.C., Gianni P., Lazard D., Mora T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993)

    Article  MATH  Google Scholar 

  13. LaValle S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)

    Book  MATH  Google Scholar 

  14. Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: Computer algebra (London, 1983). Lecture Notes in Computer Science, vol. 162, pp. 146–156. Springer, Berlin (1983)

  15. Lazard D.: Solving zero-dimensional algebraic systems. J. Symb. Comput. 13(2), 117–131 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  16. Lazard D., Rouillier F.: Solving parametric polynomial systems. J. Symb. Comput. 42(6), 636–667 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  17. McCallum, S.: An improved projection operation for cylindrical algebraic decomposition. In: Quantifier elimination and cylindrical algebraic decomposition (Linz, 1993), Texts Monogr. Symbol. Comput., pp. 242–268. Springer, Vienna (1998)

  18. Schwartz J.T., Sharir M.: On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4(3), 298–351 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  19. Strzeboński A.W.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput. 41(9), 1021–1038 (2006)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. UPMC Univ Paris 06, LIP6, 75005, Paris, France

    Daniel Lazard

  2. INRIA Paris-Rocquencourt, SALSA Project Team, 78153, Le Chesnay, France

    Daniel Lazard

  3. CNRS, LIP6, 75005, Paris, France

    Daniel Lazard

Authors
  1. Daniel Lazard
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Daniel Lazard.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lazard, D. CAD and Topology of Semi-Algebraic Sets. Math.Comput.Sci. 4, 93–112 (2010). https://doi.org/10.1007/s11786-010-0047-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11786-010-0047-0

Keywords