Frequently Asked Questions in Polyhedral Computation
http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html (original) (raw)
Komei Fukuda Swiss Federal Institute of Technology Lausanne and Zurich, Switzerland fukuda@ifor.math.ethz.ch
Date: Version June 18, 2004
![\includegraphics[height=40mm]{vtest_fig_vo.eps}](http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/img10.png)
![\includegraphics[height=40mm]{vtest_fig_vo3d.eps}](http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/img11.png)
![\includegraphics[height=40mm]{vtest_fig_vode.eps}](http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/img12.png)
- Contents
- What is Polyhedral Computation FAQ?
- Convex Polyhedron
- What is convex polytope/polyhedron?
- What are the faces of a convex polytope/polyhedron?
- What is the face lattice of a convex polytope
- What is a dual of a convex polytope?
- What is simplex?
- What is cube/hypercube/cross polytope?
- What is simple/simplicial polytope?
- What is 0-1 polytope?
- What is the best upper bound of the numbers of
-dimensional faces of a 
-polytope with 
vertices? - What is convex hull? What is the convex hull problem?
- What is the Minkowski-Weyl theorem for convex polyhedra?
- What is the vertex enumeration problem, and what is the facet enumeration problem?
- How can one enumerate all faces of a convex polyhedron?
- What computer models are appropriate for the polyhedral computation?
- How do we measure the complexity of a convex hull algorithm?
- How many facets does the average polytope with vertices in
have? - How many facets can a 0-1 polytope with vertices in have?
- How hard is it to verify that an H-polyhedron
and a V-polyhedron 
are equal? - Is there an efficient way of determining whether a given point
is in the convex hull of a given finite set 
of points in ? - How can one remove all interior points of
from for large clouds of points in ? - Is there any efficient algorithm to remove redundant inequalities from a system of linear inequalities
- Is there any efficient algorithm to compute the intersection of two (or ) polytopes
- Is there any efficient algorithm to compute the volume of a convex polytope in ?
- Voronoi Diagram and Delaunay Triangulation
- What is cell complex? What is triangulation?
- What is Voronoi diagram in ?
- What is the Delaunay triangulation in ?
- Computing the Delaunay complex and the Voronoi diagram. What does it mean and how to do it with available software?
* Sample session with cdd+ - Is it possible to compute only the adjacencies of Voronoi cells in the Voronoi diagram efficiently?
* Sample session with cdd+ - Is it possible to compute only the edges of the Delaunay complex (triangulation) ?
- Is it possible to determine the Delaunay cell containing a given point efficiently?
* Sample session with cdd+ - What is the best upper bound of the numbers of simplices in the Delaunay triangulation?
- Linear Programming
- Polyhedral Computation Codes
- Acknowledgements
- Bibliography
- About this document ...
Komei Fukuda 2004-08-26