**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 60;
2003;
219 pp;
Hardcover

MSC: Primary 14; 68;

Print ISBN: 978-0-8218-2863-2

Product Code: DIMACS/60

List Price: $80.00

Individual Member Price: $64.00

**Electronic ISBN: 978-1-4704-4018-3
Product Code: DIMACS/60.E**

List Price: $80.00

Individual Member Price: $64.00

# Algorithmic and Quantitative Real Algebraic Geometry

Share this page *Edited by *
*Saugata Basu; Laureano Gonzalez-Vega*

A co-publication of the AMS and DIMACS

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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Readership

Graduate students and research mathematicians interested in algebra and algebraic geometry and their applications.

# Table of Contents

## Algorithmic and Quantitative Real Algebraic Geometry

- Cover Cover11
- Title page i2
- Contents iii4
- Foreword v6
- Preface vii8
- Characterization and description of basic semialgebraic sets 112
- Constructive approaches to representation theorems in finitely generated real algebras 1324
- Combinatorial characterizations of algebraic sets 2334
- Lower bounds and real algebraic geometry 3546
- The Viro method applied with quadratic transforms 5566
- On the number of connected components of the relative closure of a semi-Pfaffian family 6576
- How to show a set is not algebraic 7788
- Minimizing polynomial functions 8394
- Patterns of dependence among powers of polynomials 101112
- Efficient algorithms based on critical points method 123134
- Enumerative real algebraic geometry 139150
- Combinatorial roadmaps in configuration spaces of simple planar polygons 181192
- Visibility computations: From discrete algorithms to real algebraic geometry 207218
- Back Cover Back Cover1234