scdd {rcdd} | R Documentation |
Calculate V-representation (convex hull of points and directions) of convex polytope given H-representation (intersection of half spaces) or vice versa.
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"))
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. |
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) %*% vwhere
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 |
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. |
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.
ArithmeticGMP
, ConvertGMP
,
validcdd
, makeH
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