redundant {rcdd}R Documentation

Eliminate redundant rows of H-representation and V-representation


Eliminate redundant rows from H-representation (intersection of half spaces) or V-representation (convex hull of points and directions) of convex polytope.


redundant(input, representation = c("H", "V"))


input either H-representation or V-representation of convex polyhedron (see details).
representation if "H", then input is an H-representation, otherwise a V-representation. May also be obtained from a "representation" attribute of input, if present.


See cddlibman.pdf in the doc directory of this package, especially Sections 1 and 2.

Both representations are (in R) matrices, the first two rows are special. Let foo be either an H-representation or a V-representation and

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

In the H-representation the convex polyhedron in question is the set of points x satisfying

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

In the V-representation the convex polyhedron in question is the set of points x for which there exists a lambda such that

      x <- t(lambda) %*% v
where lambda satisfies the constraints
      all(lambda * (1 - l) >= 0)
      sum(b * lambda) == max(b)

An H-representation or V-representation object can be checked for validity using the function validcdd.


a list containing some of the following components:

output The input matrix with redundant rows removed.
implied.linearity For an H-representation, row numbers of inequality constraint rows that together imply equality constraints. For a V-representation, row numbers of rays that together imply lines.
redundant Row numbers of redundant rows. Note: this is set redset output by the dd_MatrixCanonicalize function in cddlib. It apparently does not consider all rows it deletes “redundant”. Redundancy can also be determined from the following component.
new.position Integer vector of length nrow(input). Says for each input row which output row it becomes or zero to indicate redundant.

Rational Arithmetic

The input representation 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

ArithmeticGMP, ConvertGMP, validcdd, makeH


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

redundant(d2q(hrep), representation = "H")

foo <- c(1, 0, -1)
hrep <- cbind(0, 1, rep(foo, each = 9), rep(foo, each = 3), foo)
redundant(d2q(hrep), representation = "V")

[Package rcdd version 1.1 Index]