allfaces {rcdd}

All Faces of a Convex Polyhedron

Description

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

Usage

allfaces(hrep)

Arguments

hrep

H-representation of convex polyhedron (see details).

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.

Value

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. This 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.

Warning

If you want correct answers, use rational arithmetic. If you do not, this function may (1) produce approximately correct answers, (2) fail with an error, (3) give answers that are nowhere near correct with no error or warning, or (4) crash R losing all work done to that point. In large simulations (1) is most frequent, (2) occurs roughly one time in a thousand, (3) occurs roughly one time in ten thousand, and (4) has only occurred once and only with the redundant function. So the R floating point arithmetic version does mostly work, but you cannot trust its results unless you can check them independently.

See Also

scdd, ArithmeticGMP, ConvertGMP

Examples

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