allfaces {rcdd} | R Documentation |

List all the nonempty faces of a convex polyhedron, giving for each the dimension, the active set of constraints, and a relative interior point.

allfaces(hrep)

`hrep` |
H-representation of convex polyhedron (see details). |

See `cddlibman.pdf`

in the `doc`

directory of this package,
especially Sections 1 and 2.

This function lists all nonempty faces of a convex polyhedron
given by the H-representation given by the matrix `hrep`

.
Let

l <- hrep[ , 1] b <- hrep[ , 2] v <- hrep[ , - c(1, 2)] a <- (- v)

Then the convex polyhedron in question is the set of
points `x`

satisfying

axb <- a %*% x - b all(axb <= 0) all(l * axb == 0)

A nonempty *face* of a convex polyhedron *P* is the subset
of *P* that is the set of points over which some linear function
achieves its
maximum over *P*. Note that *P* is a face of *P* and appears
in the list of faces. By definition the empty set is also a face, but
is not listed. These two faces are said to be *improper*, the
other faces are *proper*.

A face in the listing is characterized by the set of constraints that
are *active*, i. e., satisfied with equality, on the face.

The *relative interior* of a convex set its its interior considered
as a subset of its affine hull. The relative interior of
a one-point set is that point. The relative interior of a multi-point
convex set is the union of open line segments *(x, y)* with endpoints
*x* and *y* in the set.

a list containing the following components:

`dimension` |
list of integers giving the dimensions of the faces. |

`active.set` |
list of integer vectors giving for each face the
set of constraints that are active (satisfied with equality) on
the face, the integers referring to row numbers of `hrep` . |

`relative.interior.point` |
list of double or character vectors
(same type as `hrep` )
giving a point in the relative interior of each face. |

The argument `hrep`

may
have type `"character"`

in which case its elements are interpreted
as unlimited precision rational numbers. They consist of an optional
minus sign, a string of digits of any length (the numerator),
a slash, and another string of digits of any length (the denominator).
The denominator must be positive. If the denominator is one, the
slash and the denominator may be omitted. The `cdd`

package
provides several functions (see ConvertGMP and ArithmeticGMP)
for conversion back and forth between R floating point numbers and rationals
and for arithmetic on GMP rationals.

`scdd`

, `ArithmeticGMP`

,
`ConvertGMP`

hrep <- rbind(c(0, 1, 1, 1, -1), c(0, 1, 1, -1, -1), c(0, 1, -1, -1, -1), c(0, 1, -1, 1, -1), c(0, 0, 0, 0, 1)) allfaces(d2q(hrep))

[Package *rcdd* version 1.1 Index]