Computing with semi-algebraic sets: Relaxation techniques and effective boundaries

C. Chen, J.H. Davenport, M. Moreno Maza, B. Xia, R. Xiao

Research output: Contribution to journalArticlepeer-review

6 Citations (SciVal)


We discuss parametric polynomial systems, with algorithms for real root classification and triangular decomposition of semi-algebraic systems as our main applications. We exhibit new results in the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 1). In order to optimize the corresponding decomposition algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of components in the output. This paper extends our earlier works ([Chen et al., 2010] and [Chen et al., 2011]).
Original languageEnglish
Pages (from-to)72-96
Number of pages25
JournalJournal of Symbolic Computation
Publication statusPublished - May 2012


Dive into the research topics of 'Computing with semi-algebraic sets: Relaxation techniques and effective boundaries'. Together they form a unique fingerprint.

Cite this