On polyhedra

The polyhedral theory derives from the theory of linear and integer programming. A convex polyhedron has two dual representations: it can be seen as the intersection of a finite number of half spaces, or as a combinations of vertices, rays and lines. The first representation is also called implicit representation while the second one is called the generators representation (as every point in a polyhedral domain can be generated by a linear combination of its generators). Motzkin [MRTT] introduced this double representation, and Chernikova  [Che65] showed how to pass from one form to the other one. Chernikova's algorithm received successive improvements which resulted eventually in an efficient computation kernel that forms the basis for polyhedra computations. Polylib uses a double description form for representing polyhedra (actually, finite unions of polyhedra). The computation of one representation from the other is realized with Chernikova's algorithm. Based on this algorithms, Polylib implements a variety of polyhedra operations, such as intersection, complement, etc. However, Polylib does more. First, it extends the concept of polyhedra to Z-polyhedra, that is to say, the intersection of polyhedra and lattices. This object was first introduced by Corinne Ancourt in her PhD thesis ("Génération de code pour multiprocesseurs à mémoires locales"). Secondly, Polylib implements Ehrhart polynomials to compute the number of integer points in a union of rational convex polytopes.