regina::NDoubleDescriptor Class Reference
[Vertex Enumeration]

Implements a modified double description method for polytope vertex enumeration. More...

#include <ndoubledescriptor.h>

List of all members.

Classes

class  LexComp
 A comparison object that helps sort hyperplanes into a good order before running the double description algorithm.
class  RaySpec
 A helper class for vertex enumeration, describing a single ray (typically a vertex in some partial solution space).

Static Public Member Functions

template<class OutputIterator >
static void enumerateExtremalRays (OutputIterator results, const NRay &rayBase, const NMatrixInt &subspace, const NEnumConstraintList *constraints, NProgressNumber *progress=0)
 Determines the extremal rays of the intersection of the n-dimensional non-negative orthant with the given linear subspace.


Detailed Description

Implements a modified double description method for polytope vertex enumeration.

For details of the underlying algorithm, see "Optimising the double description method for normal surface enumeration", Benjamin A. Burton, preprint, arXiv:0808.4050.

All routines of interest within this class are static; no object of this class should ever be created.

Python:
Not present.
Test:
Tested in the test suite, though not exhaustively.

Member Function Documentation

template<class OutputIterator >
static void regina::NDoubleDescriptor::enumerateExtremalRays ( OutputIterator  results,
const NRay rayBase,
const NMatrixInt subspace,
const NEnumConstraintList constraints,
NProgressNumber progress = 0 
) [inline, static]

Determines the extremal rays of the intersection of the n-dimensional non-negative orthant with the given linear subspace.

The resulting rays will be newly allocated and written to the given output iterator. Their deallocation is the responsibility of whoever called this routine.

The non-negative orthant is an n-dimensional cone with its vertex at the origin. The extremal rays of this cone are the n non-negative coordinate axes. This cone also has n facets, where the ith facet is the non-negative orthant of the plane perpendicular to the ith coordinate axis.

This routine takes a linear subspace, defined by the intersection of a set of hyperplanes through the origin (this subspace is described as a matrix, with each row giving the equation for one hyperplane).

The purpose of this routine is to compute the extremal rays of the new cone formed by intersecting the original cone with this linear subspace. The resulting list of extremal rays will contain no duplicates or redundancies, and they are guaranteed to be of the same subclass of NRay as the argument rayBase.

Parameter constraints may contain a set of validity constraints, in which case this routine will only return valid extremal rays. Each validity constraint is of the form "an extremal ray may only lie outside at most one of these facets of the original cone"; see the NEnumConstraintList class for details. These contraints have the important property that, although validity is not preserved under convex combination, invalidity is.

A numeric progress watcher may be passed for progress reporting. If so, this routine will poll for cancellation requests accordingly.

Parameters:
results the output iterator to which the resulting extremal rays will be written; this must accept objects of type NRay* (or alternatively pointers to the same subclass of NRay as the argument rayBase).
rayBase an arbitrary ray of the correct dimension. The real purpose of this ray is to define the class used to return solutions; in particular, the output rays will be of the same subclass of NRay as rayBase. The length of this ray must be the dimension of the space in which we are working.
subspace a matrix defining the linear subspace to intersect with the given cone. Each row of this matrix is the equation for one of the hyperplanes whose intersection forms this linear subspace. The number of columns in this matrix must be the dimension of the overall space in which we are working.
constraints a set of validity constraints as described above, or 0 if no additional constraints should be imposed.
progress a numeric progress watcher through which progress will be reported, or 0 if no progress reporting is required. If a progress watcher is passed, its expected total will be increased immediately by some number of steps and the completed total will be increased gradually by this same number. Note that NProgress::setFinished() will not be called, since whoever called this routine may need to do further processing.


The documentation for this class was generated from the following file:

Copyright © 1999-2008, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).