Macaulay2 » Documentation
Packages » FourierMotzkin :: FourierMotzkin
next | previous | forward | backward | up | index | toc

# FourierMotzkin -- for convex hull and vertex enumeration

## Description

A convex cone is polyhedral if it is a finite intersection of halfspaces. A convex cone is finitely generated if it is the set of all nonnegative linear combinations of a finite set of vectors. The fundamental theorem for cones states that a convex cone is polyhedral if and only if it is finitely generated.

FourierMotzkin is a Macaulay2 implementation of the Double Description Method (of Fourier, Dines and Motzkin) for converting between these two basic representations for convex cones. For polytopes, this allows one to convert between the convex hull of a finite point set and the bounded intersection of halfspaces.

Here are some examples illustrating some uses of this package.

- Finding the facets of the cyclic polytope
- Finding the facets of the permutahedron
- Applications to multigraded polynomial rings

This package is intended for use with relatively small polyhedra. For larger polyhedra, please consider cdd, lrs or qhull; also see polymake.

For an introduction to polyhedra and Fourier-Motzkin elimination, we recommend Chapter 2 in Gunter M. Ziegler's Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995. For historical comments, see Section 12.2 in Alexander Schrijver's Theory of Linear and Integer Programming Wiley-Interscience Series in Discrete Mathematics, John Wiley and Sons, Chichester, 1986.

We thank Rene Birkner for help debugging the package.

## Author

- Gregory G. Smith <ggsmith@mast.queensu.ca>

## Version

This documentation describes version 1.2 of FourierMotzkin, released 10 December 2008.

## Citation

If you have used this package in your research, please cite it as follows:

    @misc{FourierMotzkinSource,
      title = {{FourierMotzkin: convex hulls and polar cones. Version~1.2}},
      author = {Gregory G. Smith},
      howpublished = {A \emph{Macaulay2} package available at
        \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages}}
    }

## Exports

- Functions and commands
  - fourierMotzkin -- interchange inequality/generator representation of a polyhedral cone
- Methods
  - `fourierMotzkin(Matrix)` -- see fourierMotzkin -- interchange inequality/generator representation of a polyhedral cone
  - `fourierMotzkin(Matrix,Matrix)` -- see fourierMotzkin -- interchange inequality/generator representation of a polyhedral cone

## For the programmer

The object FourierMotzkin is a package, defined in FourierMotzkin.m2.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/FourierMotzkin.m2:297:0.