DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Sixty
TITLE: "Algorithmic and Quantitative Real Algebraic Geometry"
EDITORS: Saugata Basu and Laureano Gonzalez-Vega

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

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.

TABLE OF CONTENTS


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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on May 22, 2003.