linearity {rcdd} R Documentation

## Find implicit linearities in H-representation and V-representation of convex polyhedron

### Description

Given V-representation (convex hull of points and directions) or H-representation (intersection of half spaces) of convex polyhedron find non-linearity generators that can be made linearity without changing polyhedron

### Usage

```linearity(input, representation = c("H", "V"))
```

### Arguments

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

### Details

Interface to the function `dd_ImpliedLinearityRows` of the `cddlib` library, see `cddlibman.pdf` in the `doc` directory of this package, especially Sections 1 and 2 and page 9. See also `scdd` for a description of the way this package codes H-representations and V-representations as R matrices.

A row of a matrix that is an H-representation or V-representation is a linearity row if the first element of that row is 1. The row is an implied linearity row if the first element of that row is 0 but if it were 1 the convex polyhedron described would be unchanged.

The interpretation is as follows. For an H-representation, the linearity (given plus implied) determines the affine hull of the polyhedron (the smallest translate of a subspace containing it). For a V-representation, the linearity (given plus implied) determines the smallest affine set (translate of a subspace) contained in the polyhedron.

### Value

a numeric vector, the indices of the implied linearity rows. (Note: rows that are linearity rows in the input matrix are not contained in this vector.)

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

`ArithmeticGMP`, `ConvertGMP`, `validcdd`, `makeH`

### Examples

```### calculate affine hull
### determined by given + implied linearity rows
qux <- rbind(c(0, 2, 0, 0, 1),
c(0, 3, 1, 0, 0),
c(0, 4, 0, 1, 0),
c(0, -7, -1, -1, 0))
out <- linearity(qux, representation = "H")
print(out)
qux[out, 1] <- 1
redundant(qux, representation = "H")\$output

### calculate minimal nonempty face of polyhedral convex cone
### determined by given + implied linearity rows
qux <- rbind(c(0, 0, 0, 0, 1),
c(0, 0, 1, 0, 0),
c(0, 0, 0, 1, 0),
c(0, 0, -1, -1, 0))
out <- linearity(qux, representation = "V")
print(out)
redundant(qux, representation = "V")\$output
```

[Package rcdd version 1.1 Index]