# HParallelotope

`LazySets.HParallelotope`

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

Type that represents a parallelotope in constraint form.

**Fields**

`directions`

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

– vector such that each element is the offset of the corresponding constraint

**Notes**

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

type represents parallelotopes in constraint form.

The constraint form of a parallelotope is described next. Let $D ∈ \mathbb{R}^{n × n}$ be a matrix and let $c ∈ \mathbb{R}^{2n}$ be a vector. The parallelotope $P ⊂ \mathbb{R}^n$ generated by the directions matrix $D$ and the offset vector $c$ is given by the set of points $x ∈ \mathbb{R}^$ 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$.

For details on the notions given in these notes 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.

`LazySets.directions`

— Method`directions(P::HParallelotope)`

Return the directions matrix of a parallelotope.

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

— Method`offset(P::HParallelotope)`

Return the offsets of a parallelotope.

**Input**

`P`

– parallelotope in constraint representation

**Output**

A vector with the $2n$ offsets of the parallelotope, if $n$ is the dimension of $P$.

`LazySets.dim`

— Method`dim(P::HParallelotope)`

Return the dimension of a parallelotope.

**Input**

`P`

– parallelotope in constraint representation

**Output**

An integer representing the dimension of the parallelotope

`LazySets.base_vertex`

— Method`base_vertex(P::HParallelotope)`

Compute the base vertex of the given 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, \ldots, 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.extremal_vertices`

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

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

**Input**

`P`

– parallelotope in constraint representation

**Output**

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

**Algorithm**

Let $P$ be a parallelotope in constraint representation with directions matrix $D$ and offset vector $c$. We denote the *extremal vertices* of $P$ with respect to its base vertex $q$ to be those vertices of $P$ which have an edge in common with $q$. 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, \ldots, n$, $v_i = [-c_{n+1}, \ldots, c_i, \ldots, -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.center`

— Method`center(P::HParallelotope)`

Return the center of a parallelotope.

**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, \ldots, n$. Then the center is located at

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

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

`LazySets.genmat`

— Method`genmat(P::HParallelotope)`

Return the generator matrix of a parallelotope.

**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, \ldots, 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, \ldots, n$.

`LazySets.generators`

— Method`generators(P::HParallelotope)`

Return an iterator over the generators of a parallelotope.

**Input**

`P`

– parallelotope in constraint representation

**Output**

An iterator over the generators of `P`

.

`LazySets.constraints_list`

— Method`constraints_list(H::AbstractHyperrectangle{N}) where {N}`

Return the list of constraints of an axis-aligned hyperrectangular set.

**Input**

`H`

– hyperrectangular set

**Output**

A list of linear constraints.

`constraints_list(P::Ball1{N}) where {N}`

Return the list of constraints defining a ball in the 1-norm.

**Input**

`B`

– ball in the 1-norm

**Output**

The list of constraints of the ball.

**Algorithm**

The constraints can be defined as $d_i^T (x-c) ≤ r$ for all $d_i$, where $d_i$ is a vector with elements $1$ or $-1$ in $n$ dimensions. To span all possible $d_i$, the function `Iterators.product`

is used.

`constraints_list(x::Interval{N}) where {N}`

Return the list of constraints of the given interval.

**Input**

`x`

– interval

**Output**

The list of constraints of the interval represented as two one-dimensional half-spaces.

`constraints_list(L::Line{N, VN}) where {N, VN}`

Return the list of constraints of a line.

**Input**

`L`

– line

**Output**

A list containing `2n-2`

half-spaces whose intersection is `L`

, where `n`

is the ambient dimension of `L`

.

`constraints_list(U::Universe{N}) where {N}`

Return the list of constraints defining a universe.

**Input**

`U`

– universe

**Output**

The empty list of constraints, as the universe is unconstrained.

`constraints_list(P::HParallelotope{N, VN}) where {N, VN}`

Return the list of constraints of the given parallelotope.

**Input**

`P`

– parallelotope in constraint representation

**Output**

The list of constraints of `P`

.

constraints_list(cpa::CartesianProductArray{N}) where {N}

Return the list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

**Input**

`cpa`

– Cartesian product array

**Output**

A list of constraints.

`constraints_list(ia::IntersectionArray{N}) where {N}`

Return the list of constraints of an intersection of a finite number of (polyhedral) sets.

**Input**

`ia`

– intersection of a finite number of (polyhedral) sets

**Output**

The list of constraints of the intersection.

**Notes**

We assume that the underlying sets are polyhedral, i.e., offer a method `constraints_list`

.

**Algorithm**

We create the polyhedron from the `constraints_list`

s of the sets and remove redundant constraints.

`constraints_list(rm::ResetMap{N}) where {N}`

Return the list of constraints of a polytopic reset map.

**Input**

`rm`

– reset map of a polytope

**Output**

The list of constraints of the reset map.

**Notes**

We assume that the underlying set `X`

is a polytope, i.e., is bounded and offers a method `constraints_list(X)`

.

**Algorithm**

We fall back to `constraints_list`

of a `LinearMap`

of the `A`

-matrix in the affine-map view of a reset map. Each reset dimension $i$ is projected to zero, expressed by two constraints for each reset dimension. Then it remains to shift these constraints to the new value.

For instance, if the dimension $5$ was reset to $4$, then there will be constraints $x₅ ≤ 0$ and $-x₅ ≤ 0$. We then modify the right-hand side of these constraints to $x₅ ≤ 4$ and $-x₅ ≤ -4$, respectively.

`constraints_list(rm::ResetMap{N, S}) where {N, S<:AbstractHyperrectangle}`

Return the list of constraints of a hyperrectangular reset map.

**Input**

`rm`

– reset map of a hyperrectangular set

**Output**

The list of constraints of the reset map.

**Algorithm**

We iterate through all dimensions. If there is a reset, we construct the corresponding (flat) constraints. Otherwise, we construct the corresponding constraints of the underlying set.

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

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

Inherited from `ConvexSet`

:

Inherited from `AbstractPolytope`

:

Inherited from `AbstractCentrallySymmetricPolytope`

:

Inherited from `AbstractZonotope`

: