Up: Directory of Computational Geometry Software

Numerical and algebraic computation

Robust floating-point predicates

 C subroutines to compute orientation and in-circle tests on floating-point inputs. Adaptive floating point arithmatic evaluates only to the precision required to return the correct yes or no answer.

For an explaination of the predicates and the software itself, see the Web page. Also contains pointers to the papers explaining how they work.

Developed by Jonathan Shewchuck for the Triangle program.

Real/Expr

 Exact arithmetic computation package. Implementation of C++ classes for real numbers and expressions. Automatically evaluates comparisons to the precision required to get it right, or allows the user to specify the level of precision in expression evaluation. Handles +,-,*,/,sqrt on regular floats, BigInts, Rationals and BigFloats, with some smarts for efficiency.

By Chee Yap, Tom Dube, and Kouji Ouchi.

See their homepage for more info and links to the code.

Exact determinant testing

 C++ libraries to find the exact sign of 2x2 and 3x3 integer matrix determinants.

By F. Avnaim,J-D. Boissonnat,O. Devillers, F. Preparata, and M. Yvinec, INRIA.

See the Web page for more information and the code.

The Detri program includes a long-integer arithmatic package (+,-,*) and the Simulation of Simplicity library. This is the closest thing I know of to an (implemented) ``black box'' for removing degeneracies from a point set by symbolic perturbation. Both in C.

Toolkit for Algebra and Geometry

 Resultants, sub-resultants and Sturm-Habicht sequences for multivariate polynomials over floating-point numbers, integers modulo a prime, straight-line programs or mixed-arithmetic. Use to solve systems of polynomial equalities.

Take a look at the paper for an overview. There is also documentation and the text of the relevant papers at the ftp site.

By Ashu Rege and John Canny, U.C. Berkeley.
Get the toolkit by ftp from Berkeley.

Sparse resultants and mixed volumes

 Sparse polynomial system solver based on the Newton resultant, which finds all common solutions for a system of polynomials. This is apparently more efficient than Gröbner bases for polynomials of high degree with few terms. Also programs to compute the mixed volume and mixed subdivision of sets of polytopes. These can be used to count the roots of polynomials.

Mostly by Ioannis Z. Emiris, now at INRIA, and John F. Canny, UC Berkeley.

Documentation, papers and code are here.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu
Created: May 31 1995 --- Last modified: Thu Jun 1 14:24:44 1995