Computing with semi-algebraic sets represented by triangular decomposition

Changbo Chen, James H Davenport, Marc Moreno Maza, Bican Xia, Rong Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)
139 Downloads (Pure)

Abstract

This article is a continuation of our earlier work [3], which introduced triangular decompositions of semi-algebraic systems and algorithms for computing them. Our new contributions include theoretical results based on which we obtain practical improvements for these decomposition algorithms. We exhibit new results on the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its "true boundary" (Definition 2). In order to optimize these algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of redundant components in the output. Moreover, we present procedures for basic set-theoretical operations on semi-algebraic sets represented by triangular decomposition. Experimentation confirms the effectiveness of our techniques.
Original languageEnglish
Title of host publicationISSAC '11 Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Pages75-82
Number of pages8
ISBN (Print)9781450306751
DOIs
Publication statusPublished - 2011
Event36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011 - San Jose, CA, USA United States
Duration: 1 Jan 2011 → …

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
PublisherAssociation for Computing Machinery

Conference

Conference36th International Symposium on Symbolic and Algebraic Computation, ISSAC 2011, June 8, 2011 - June 11, 2011
CountryUSA United States
CitySan Jose, CA
Period1/01/11 → …

Fingerprint Dive into the research topics of 'Computing with semi-algebraic sets represented by triangular decomposition'. Together they form a unique fingerprint.

Cite this