allfaces {rcdd} R Documentation

## 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. 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`

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

[Package rcdd version 1.1 Index]