Regina Calculation Engine
Static Public Member Functions | List of all members
regina::NMaxAdmissible Class Reference

Used to enumerate all maximal admissible faces of a polyhedral cone under a given set of admissibility constraints. More...

#include <enumerate/nmaxadmissible.h>

Static Public Member Functions

template<class BitmaskType , class RayIterator >
static std::vector< BitmaskType > * enumerate (RayIterator beginExtremalRays, RayIterator endExtremalRays, const NEnumConstraintList *constraints)
 Enumerates all maximal admissible faces of the given polyhedral cone. More...
 

Detailed Description

Used to enumerate all maximal admissible faces of a polyhedral cone under a given set of admissibility constraints.

See the routine enumerate() for details.

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

Python:
Not present.

Member Function Documentation

template<class BitmaskType , class RayIterator >
static std::vector<BitmaskType>* regina::NMaxAdmissible::enumerate ( RayIterator  beginExtremalRays,
RayIterator  endExtremalRays,
const NEnumConstraintList constraints 
)
static

Enumerates all maximal admissible faces of the given polyhedral cone.

The cone must be the intersection of the non-negative orthant in some Euclidean space R^n with a linear subspace.

Admissibility is defined by the given set of constraints. Each constraint requires that at most one of a given set of coordinates can be non-zero; see the NEnumConstraintList class for details. In particular, the quadrilateral constraints from normal surface theory are of this type.

It is simple to show that the admissible region of the cone is a union of faces, which we call "admissible faces". Those admissible faces that do not appear as a strict subface of some other admissible face are called "maximal admissible faces". The admissible region can therefore be expressed as the union of all maximal admissible faces.

The input for this routine is the set of all admissible extremal rays of the cone. These should be computed beforehand; for instance, using the routine NDoubleDescription::enumerateExtremalRays().

The return value is the set of all maximal admissible faces, stored in a newly allocated vector. Each face F is described by a bitmask. Specifically: if we are working in R^n, then each face is described by a bitmask b of length n, where b[i] is false if every point x in F has x[i]=0, and b[i] is true if every point x in the relative interior of F has x[i] > 0.

Precondition
The template argument RayIterator should be an iterator type that, when dereferenced, can be cast to a const NRay*.
The template argument BitmaskType is one of the bitmask types NBitmask, NBitmask1 or NBitmask2.
Bitmasks of type BitmaskType can hold n bits, where n is the dimension of the underlying space (i.e., the size of the input vectors described by beginExtremalRays and endExtremalRays). This is always true of NBitmask, but you must be careful when using one of the fast but size-limited types NBitmask1 or NBitmask2.
Parameters
beginExtremalRaysan iterator that begins the set of admissible extremal rays, as described above. Typically this would be rays.begin() if rays is a standard container type.
endExtremalRaysan iterator that is past-the-end of the set of admissible extremal rays. Typically this would be rays.end() if rays is a standard container type.
constraintsa set of validity constraints as described above. This may be 0 to indicate no constraints (in which case there will be just one maximal admissible face).
Returns
a newly allocated list containing one bitmask representing each maximal admissible face, as described above.

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

Copyright © 1999-2014, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).