# HParallelotope

`LazySets.HParallelotopeModule.HParallelotope`

— Type`HParallelotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}} <: AbstractZonotope{N}`

Type that represents a parallelotope in constraint form.

**Fields**

`directions`

– square matrix where each row is the direction of two parallel constraints`offset`

– vector where each element is the offset of the corresponding constraint

**Notes**

Parallelotopes are centrally symmetric convex polytopes in $ℝ^n$ having $2n$ pairwise parallel constraints. Every parallelotope is a zonotope. As such, parallelotopes can be represented in constraint form or in generator form. The `HParallelotope`

type represents parallelotopes in constraint form.

Let $D ∈ ℝ^{n × n}$ be a matrix and let $c ∈ ℝ^{2n}$ be a vector. The parallelotope $P ⊂ ℝ^n$ generated by the directions matrix $D$ and the offset vector $c$ is given by the set of points $x ∈ ℝ^n$ such that:

\[ D_i ⋅ x ≤ c_{i},\text{ and } -D_i ⋅ x ≤ c_{n+i}\]

for $i = 1, …, n$. Here $D_i$ represents the $i$-th row of $D$ and $c_i$ the $i$-th component of $c$.

Note that, although representing a zonotopic set, an `HParallelotope`

can be empty or unbounded if the constraints are unsuitably chosen. This may cause problems with default methods because the library assumes that zonotopic sets are non-empty and bounded. Thus such instances are considered illegal. The default constructor thus checks these conditions, which can be deactivated by passing the argument `check_consistency=false`

.

For details as well as applications of parallelotopes in reachability analysis we refer to [1] and [2]. For conversions between set representations we refer to [3].

**References**

[1] Tommaso Dreossi, Thao Dang, and Carla Piazza. *Reachability computation for polynomial dynamical systems.* Formal Methods in System Design 50.1 (2017): 1-38.

[2] Tommaso Dreossi, Thao Dang, and Carla Piazza. *Parallelotope bundles for polynomial reachability.* Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control. ACM, 2016.

[3] Matthias Althoff, Olaf Stursberg, and Martin Buss. *Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes.* Nonlinear analysis: hybrid systems 4.2 (2010): 233-249.

## Conversion

`Base.convert`

— Method`convert(::Type{HParallelotope}, Z::AbstractZonotope{N}) where {N}`

Convert a zonotopic set of order one to a parallelotope in constraint representation.

**Input**

`HParallelotope`

– target type`Z`

– zonotopic set of order one

**Output**

A parallelotope in constraint representation.

**Notes**

This function requires that the list of constraints of `Z`

are obtained in the particular order returned from the `constraints_list`

function of a `Zonotope`

. Hence it first converts `Z`

to a `Zonotope`

.

## Operations

`LazySets.HParallelotopeModule.base_vertex`

— Method`base_vertex(P::HParallelotope)`

Compute the base vertex of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The base vertex of `P`

.

**Algorithm**

Intuitively, the base vertex is the point from which we get the relative positions of all the other points. The base vertex can be computed as the solution of the $n$-dimensional linear system $D_i x = c_{n+i}$ for $i = 1, …, n$, see [1, Section 3.2.1].

[1] Dreossi, Tommaso, Thao Dang, and Carla Piazza. *Reachability computation for polynomial dynamical systems.* Formal Methods in System Design 50.1 (2017): 1-38.

`LazySets.API.center`

— Method`center(P::HParallelotope)`

Return the center of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The center of the parallelotope.

**Algorithm**

Let $P$ be a parallelotope with base vertex $q$ and list of extremal vertices with respect to $q$ given by the set $\{v_i\}$ for $i = 1, …, n$. Then the center is located at

\[ c = q + ∑_{i=1}^n \frac{v_i - q}{2} = q (1 - \frac{2}) + \frac{s}{2},\]

where $s := ∑_{i=1}^n v_i$ is the sum of extremal vertices.

`LazySets.API.constraints_list`

— Method`constraints_list(P::HParallelotope)`

Return the list of constraints of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The list of constraints of `P`

.

`LazySets.API.dim`

— Method`dim(P::HParallelotope)`

Return the dimension of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The ambient dimension of the parallelotope.

`LazySets.HParallelotopeModule.directions`

— Method`directions(P::HParallelotope)`

Return the directions matrix of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

A matrix where each row represents a direction of the parallelotope. The negated directions `-D_i`

are implicit (see `HParallelotope`

for details).

`LazySets.HParallelotopeModule.extremal_vertices`

— Method`extremal_vertices(P::HParallelotope{N, VN}) where {N, VN}`

Compute the extremal vertices with respect to the base vertex of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The list of vertices connected to the base vertex of $P$.

**Notes**

Let $P$ be a parallelotope in constraint representation with directions matrix $D$ and offset vector $c$. The *extremal vertices* of $P$ with respect to its base vertex $q$ are those vertices of $P$ that have an edge in common with $q$.

**Algorithm**

The extremal vertices can be computed as the solution of the $n$-dimensional linear systems of equations $D x = v_i$ where for each $i = 1, …, n$, $v_i = [-c_{n+1}, …, c_i, …, -c_{2n}]$.

We refer to [1, Section 3.2.1] for details.

[1] Tommaso Dreossi, Thao Dang, and Carla Piazza. *Reachability computation for polynomial dynamical systems.* Formal Methods in System Design 50.1 (2017): 1-38.

`LazySets.generators`

— Method`generators(P::HParallelotope)`

Return an iterator over the generators of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

An iterator over the generators of `P`

.

`LazySets.genmat`

— Method`genmat(P::HParallelotope)`

Return the generator matrix of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

A matrix where each column represents one generator of the parallelotope `P`

.

**Algorithm**

Let $P$ be a parallelotope with base vertex $q$ and list of extremal vertices with respect to $q$ given by the set $\{v_i\}$ for $i = 1, …, n$. Then, the $i$-th generator of $P$, represented as the $i$-th column vector $G[:, i]$, is given by:

\[ G[:, i] = \frac{v_i - q}{2}\]

for $i = 1, …, n$.

`LazySets.HParallelotopeModule.offset`

— Method`offset(P::HParallelotope)`

Return the offsets of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

A vector with the $2n$ offsets of the parallelotope, where $n$ is the dimension of `P`

.

`Base.rand`

— Method```
rand(::Type{HParallelotope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
[rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)
```

Create a random parallelotope in constraint representation.

**Input**

`HParallelotope`

– type for dispatch`N`

– (optional, default:`Float64`

) numeric type`dim`

– (optional, default: 2) dimension`rng`

– (optional, default:`GLOBAL_RNG`

) random number generator`seed`

– (optional, default:`nothing`

) seed for reseeding

**Output**

A random parallelotope.

**Notes**

All numbers are normally distributed with mean 0 and standard deviation 1.

**Algorithm**

The directions matrix and offset vector are created randomly. On average there is a good chance that this resulting set is empty. We then modify the offset to ensure non-emptiness.

There is a chance that the resulting set represents an unbounded set. This implementation checks for that case and then samples a new set.

`LazySets.API.volume`

— Method`volume(P::HParallelotope)`

Return the volume of a parallelotope in constraint representation.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The volume.

**Algorithm**

The volume of an $n$-dimensional parallelotope `P`

is $2^n · |\det(G)|$, where $G$ is the generator matrix of `P`

. This can be seen as follows: The generator matrix transforms the $n$-dimensional hypercube $[0, 1]^n$ to a parallelotope of volume $|\det(G)|$. Since the representation of a parallelotope instead transforms the hypercube $[-1, 1]^n$, this result has to be doubled for each dimension.

Inherited from `LazySet`

:

Inherited from `AbstractPolytope`

:

Inherited from `AbstractCentrallySymmetricPolytope`

:

Inherited from `AbstractZonotope`

: