Polylib - A library of polyhedral functions
Introduction to Polyhedra
Polyhedra are geometric representations of linear systems of
equations and inequalities. The polyhedral library is a set of
functions which operate on objects made of finite unions of polyhedra.
There is interest in polyhedra in connection with a wide range of
diverse applications.
Polyhedra have been studied in several fields:
- from the geometric point of view by computational geometrists
- from the algebraic point of view by the operations research and
linear programming communities
- and from the structural/lattice point of view by the combinatorics
community.
Polylib
The polyhedral library (or polylib for short)
operates on objects made up of unions of polyhedra of any dimension.
It was developed at IRISA, in Rennes, France in connection with
the ALPHA project. However, it was written
to be general purpose and has since been used by many other projects.
It differs from other libraries in that it is designed to do computations
on finite unions of polyhedra.
The following polyhedral operations are supported in polylib:
- Intersection
- Union
- Difference
- Simplification (widening) of a polyhedron in the context of
another polyhedron
- Convex hull
- Image by an affine multidimensional transformation function
- Preimage by an affine multidimensional transformation function
- Creation of a polyhedron from a list of mixed constraints (equalities
and inequalities).
- Creation of a polyhedron from a list of vertices, rays, and lines.
- Creation of an empty polyhedron.
- Creation of a universe polyhedron.
Polyhedra are represented internally in their full dual form as a list of
- mixed constraints: equalities and inequalities
- geometric features: vertices, rays, and lines
Polylib was originally written in 1993 and
was based on the Motzkin Double-Description method for finding
the dual representation of a polyhedron and on an implementation of
Chernikova's algorithm written by Herve LeVerge.
(Herve died tragically in an accident in 1994).
Since then, it has undergone many revisions and corrections.
In 1995, I joined the faculty at BYU where I continue to support the
library.
The library is written in C and all of the operations are C-callable
procedures. Thus, the library can be embedded in other larger systems.
The library is currently supported by Vincent Lochner. Source code for the
polylib can be downloaded from the new
PolyLib
site.
Other Related Projects (in no particular order)
- Parma Polyhedra Library
The Parma Polyhedra Library
(PPL) is a C++ library for the manipulation of convex polyhedra.
It might be considered a second generation library, as they studied previous
polyhedral libraries (including Polylib), combined ideas, and produced this new
library. It also includes an excellent bibliography.
- Convex
Written by
Matthias Franz
Convex Homepage
Convex
is a Maple package to facilitate computations in convex geometry.
Its provides functions to deal with rational polyhedral cones, polytopes, general polyhedra,
faces of one of the above, and fans of arbitrary dimension or size.
- Polka
Written by
Nicolas Halbwach
Readme
Nicolas Halbwach's paper describing POLKA
Polka
Homepage
- Porta
Porta
Homepage and the
Old Porta Homepage
Written by
Thomas Christof, and revised by
Andreas Lobel and Mechthild Stoer.
Readme
- Omega
The Omega Project by William Pugh
- Cdd
Cdd Homepage
Written by
Komei Fukuda
- Polymake
Polymake homepage
Written by
Günter M. Ziegler
- lrs
lrs Homepage
Written by
David Avis
- qhull
Qhull computes convex hulls,
Delaunay triangulations, halfspace intersections about a point,
Voronoi diagrams, furthest-site Delaunay triangulations,
and furthest-site Voronoi diagrams.
It runs in 2-d, 3-d, 4-d, and higher dimensions.
It implements the Quickhull algorithm for computing the convex hull.
Qhull handles roundoff errors from floating point arithmetic.
It computes volumes, surface areas, and approximations to the convex hull.
Other Links of Interest
Last updated in August 2004
Doran Wilde wilde@ee.byu.edu