Last update: July 23, 2002

BACK

Publications on general topics in Computational Geometry :

• Cox, David et al. :
  • Using algebraic geometry, 1998.
  • Ideals, Varieties, and Algorithms, 2nd ed. 1996.
• Devroye, Luc:
  • Lecture Notes on Bucket Algorithms, 1986.
• Gerald Farin et al. :
  • The Geometry Toolbox - for Graphics and Modeling, 1998.
• Smid, Michiel :
  • Closest-point problems in computational geometry, 2000.

BibTeX references.

Web link

In recent years, the discovery of new algorithms for dealing with polynomial equations, coupled with their implementation on fast inexpensive computers, has sparked a minor revolution in the study and practice of algebraic geometry. These algorithmic methods have also given rise to some exciting new applications of algebraic geometry. One of the goals of this book is to illustrate the many uses of algebraic geometry and to highlight the more recent applications of Groebner bases and resultants. In order to do this, the authors provide an introduction to some algebraic objects and techniques more advanced than one typically encounters in a first course, but which are nonetheless of great utility. This book is accessible to nonspecialists and to readers with a diverse range of backgrounds. This book is written at the graduate level and hence assumes the reader knows the material covered in standard undergraduate courses, including abstract algebra. But because the text is intended for beginning graduate students, it does not require graduate algebra, and in particular, does not assume that the reader is familiar with modules.

Contents:

Introduction.- Solving Polynomial Equations.- Resultants.- Computation in Local Rings.- Modules.- Free Resolutions.- Polytopes, Resultants and Equations.- Integer Programming, Combinatorics and Splines.- Algebraic Coding Theory.

Web link

Chapter 1: Geometry, Algebra, and Algorithms

1. Polynomials and Affine Space
2. Affine Varieties
3. Parametrizations of Affine Varieties
4. Ideals
5. Polynomials of One Variable

Chapter 2: Groebner Bases

1. Introduction
2. Orderings on the Monomials in k[x1,...,xn]
3. A Division Algorithm in k[x1,...,xn]
4. Monomial Ideals and Dickson's Lemma
5. The Hilbert Basis Theorem and Groebner Bases
6. Properties of Groebner Bases
7. Buchberger's Algorithm
8. First Applications of Groebner Bases
9. (Optional) Improvements on Buchberger's Algorithm

Chapter 3: Elimination Theory

1. The Elimination and Extension Theorems
2. The Geometry of Elimination
3. Implicitization
4. Singular Points and Envelopes
5. Unique Factorization and Resultants
6. Resultants and the Extension Theorem

Chapter 4: The Algebra-Geometry Dictionary

1. The Nullstellensatz
2. Radical Ideals and the Ideal-Variety Correspondence
3. Sums, Products, and Intersections of Ideals
4. Zariski Closure and Quotients of Ideals
5. Irreducible Varieties and Prime Ideals
6. Decomposition of a Variety into Irreducibles
7. (Optional) Primary Decomposition of Ideals
8. .Summary

Chapter 5: Polynomial and Rational Functions on a Variety

1. Polynomial Mappings
2. Quotients of Polynomials Rings
3. Algorithmic Computations in k[x1,...,xn]/I
4. The Coordinate Ring of an Affine Variety
5. Rational Functions on a Variety
6. (Optional) Proof of the Closure Theorem (New in the Second Edition)

Chapter 6: Robotics and Automatic Geometric Theorem Proving

1. Geometric Description of Robots
2. The Forward Kinematics Problem
3. The Inverse Kinematic Problem and Motion Planning
4. Automatic Geometric Theorem Proving
5. Wu's Method

Chapter 7: Invariant Theory of Finite Groups

1. Symmetric Polynomials
2. Finite Matrix Groups and Rings of Invariants
3. Generators for the Ring of Invariants
4. Relations among Generators and the Geometry of Orbits

Chapter 8: Projective Algebraic Geometry

1. The Projective Plane
2. Projective Space and Projective Varieties
3. The Projective Algebra-Geometry Dictionary
4. The Projective Closure of an Affine Variety
5. Projective Elimination Theory
6. The Geometry of Quadric Hypersurfaces
7. Bezout's Theorem (New in the Second Edition)

Chapter 9: The Dimension of a Variety

1. The Variety of a Monomial Ideal
2. The Complement of a Monomial Ideal
3. The Hilbert Function and the Dimension of a Variety
4. Elementary Properties of Dimension
5. Dimension and Algebraic Independence
6. Dimension and Nonsingularity
7. The Tangent Cone

Appendix A: Some Concepts from Algebra

1. Fields and Rings
2. Groups
3. Determinants

Appendix B: Pseudocode

1. Inputs, Outputs, Variables and Constants
2. Assignment Statements
3. Looping Structures
4. Branching Structures

Appendix C: Computer Algebra Systems

1. AXIOM (New in the Second Edition)
2. Maple
3. Mathematica
4. REDUCE
5. Other Systems

Appendix D: Independent Projects

1. General Comments
2. Suggested Projects

References

Index

Web link

A comprehensive overview is given of algorithms and data structures for proximity problems on point sets in IR^D . In particular, the closest pair problem, the exact and approximate post-office problem, and the problem of constructing spanners are discussed in detail.

Page created & maintained by Frederic Leymarie, 2000-2.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu