This is an FAQ to answer some basic questions arising from certain geometric computation in general dimensional (mostly Euclidean) space. The main areas to be covered are the convex hull computation of a finite point set, the vertex enumeration for a convex polytope, the computation of Voronoi diagram and Delaunay triangulation, in . We illustrate typical solution processes with small examples and publicly available codes such as cdd+ and lrs.
It is still incomplete and perhaps contains a number of typos and mistakes at this moment, but I will try to make it as complete as possible for the primary purposes.
We do not intend to discuss techniques and algorithms specially designed for particular dimensions (e.g. 2D and 3D). For those interested primarily in geometric computation in lower dimensions (e.g. 2 and 3) should consult the comp.graphics.algorithms FAQ [O'R] as well as a handbook of discrete and computational geometry [Ge97].
Please note that the Polyhedral Computation FAQ is available from [Fuk] in two formats, ps and html. (A pdf version will be available soon). The html version is created by latex2html, and it has an advantage of having html links within the documents. Yet, one has to be aware of the fact that some conversion errors exist that give wrong equation numberings and missing figures. Please consider the ps version as the most reliable source.
To refer to this document, please use
Komei FukudaPlease send your comments to email@example.com
Polyhedral computation FAQ
Swiss Federal Institute of Technology
Lausanne and Zurich, Switzerland