rcdd (version 1.1-4)

scdd: Go between H-representation and V-representation of convex polyhedron

Description

Calculate V-representation (convex hull of points and directions) of convex polytope given H-representation (intersection of half spaces) or vice versa.

Usage

scdd(input, adjacency = FALSE, inputadjacency = FALSE,
    incidence = FALSE, inputincidence = FALSE, roworder = c("lexmin",
    "maxindex", "minindex", "mincutoff", "maxcutoff", "mixcutoff", "lexmax",
    "randomrow"), keepinput = c("maybe", "TRUE", "FALSE"),
    representation = c("H", "V"))

Arguments

input

either H-representation or V-representation of convex polyhedron (see details).

adjacency

if TRUE produce adjacency list of output generators.

inputadjacency

if TRUE produce adjacency list of input generators.

incidence

if TRUE produce incidence list of output generators with respect to input generators.

inputincidence

if TRUE produce incidence list of input generators with respect to output generators.

roworder

during the computation, take input rows in the specified order. The default "lexmin" is usually o. k. The option "maxcutoff" might be efficient if the input contains many redundant inequalities or generators.

keepinput

if "TRUE" or "maybe" and an adjacency or incidence list involving the input is requested, save the input.

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.

Value

• a list containing some of the following components:
• output
  An H-representation if input was V-representation and vice versa.
• input
  The argument input, if requested.
• adjacency
  The adjacency list, if requested.
• inputadjacency
  The input adjacency list, if requested.
• incidence
  The incidence list, if requested.
• inputincidence
  The input incidence list, if requested.

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.

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

Details

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

Both representations are (in R) matrices, the first two columns 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)<="" p="">

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.

See Also

ArithmeticGMP, ConvertGMP, validcdd, makeH

Examples

d <- 4
# unit simplex in H-representation
qux <- makeH(- diag(d), rep(0, d), rep(1, d), 1)
print(qux)
# unit simplex in V-representation
out <- scdd(qux)
print(out)
# unit simplex in H-representation
# note: different from original, but equivalent
out <- scdd(out$output)
print(out)

# add equality constraint
quux <- addHeq(1:d, (d + 1) / 2, qux)
print(quux)
out <- scdd(quux)
print(out)

# use some options
out <- scdd(quux, roworder = "maxcutoff", adjacency = TRUE)
print(out)

# convex hull
np <- 50
x <- matrix(rnorm(d * np), ncol = d)
foo <- cbind(0, cbind(1, x))
out <- scdd(d2q(foo), inputincidence = TRUE, representation = "V")
boundies <- sapply(out$inputincidence, length) > 0
sum(boundies) ## number of points on boundary of convex hull