scdd {rcdd} | R Documentation |
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 |
inputadjacency |
if |
incidence |
if |
inputincidence |
if |
roworder |
during the computation, take input rows in the specified
order. The default |
keepinput |
if |
representation |
if |
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)
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
.
Value
a list containing some of the following components:
output |
An H-representation if input was V-representation and vice versa. |
input |
The argument |
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. 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
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
# not the efficient way to do convex hull
# see ?redundant and sections 5.4 and 6.2 of the package vignette
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