Discrete Mathematics and Theoretical Computer Science

TITLE: "Algorithmic and Quantitative Real Algebraic Geometry"

EDITORS: Saugata Basu and Laureano Gonzalez-Vega

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

Algorithmic and quantitative aspects in real algebraic geometry are becoming increasingly important areas of research because of their roles in other areas of mathematics and computer science. The papers in this volume collectively span several different areas of current research.

The articles are based on talks given at the DIMACS Workshop on "Algorithmic and Quantitative Aspects of Real Algebraic Geometry". Topics include deciding basic algebraic properties of real semi-algebraic sets, application of quantitative results in real algebraic geometry towards investigating the computational complexity of various problems, algorithmic and quantitative questions in real enumerative geometry, new approaches towards solving decision problems in semi-algebraic geometry, as well as computing algebraic certificates, and applications of real algebraic geometry to concrete problems arising in robotics and computer graphics. The book is intended for researchers interested in computational methods in algebra.

Forward v Preface vii Characterization and description of basic semialgebraic sets C. Andradas 1 Constructive approaches to representation theorems in finitely generated real algebras Dionne Bailey and Victoria Powers 13 Combinatorial characterizations of algebraic sets Isabelle Bonnard 23 Lower bounds and real algebraic geometry Peter Burgisser 35 The Viro method applied with quadratic transforms Benoit Chevallier 55 On the number of connected components of the relative closure of a semi-Pfaffian family Andrei Gabrielov and Thierry Zell 65 How to show a set is not algebraic Clint McCrory 77 Minimizing polynomial functions Pablo A. Parrilo and Bernd Sturmfels 83 Patterns of dependence among powers of polynomials Bruce Reznick 101 Efficient algorithms based on critical points method Fabrice Rouillier 123 Enumerative real algebraic geometry Frank Sottile 139 Combinatorial roadmaps in configuration spaces of simple planar polygons Ileana Streinu 181 Visibility computations: From discrete algorithms to real algebraic geometry Thorsten Theobald 207

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on May 22, 2003.