allfaces {rcdd}R Documentation

All Faces of a Convex Polyhedron


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




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.

Rational Arithmetic

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.

See Also

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))


[Package rcdd version 1.1 Index]