The Convex Geometry of Integrator Reach Sets
Shadi Haddad Abhishek Halder


The Two-sided Jet Structures of NGC 1052 at Scales from 300 to 4 × 10^7 Schwarzschild Radii
    [
    Received: date / Accepted: date
===========================================================================================

empty
empty




We study the convex geometry of the forward reach sets for integrator dynamics in finite dimensions with bounded control. We derive closed-form expressions for the volume and the diameter (i.e., maximal width) of these sets in terms of the state space dimension, control bound, and time. These results are novel, and use convex analysis to give an analytical handle on the “size" of the integrator reach set. Several concrete examples are provided to illustrate our results. We envision that the ideas presented here will motivate further theoretical and algorithmic development in reach set computation. 






§ INTRODUCTION

We consider the d-dimensional integrator dynamics

    ẋ = Ax + bu,   x∈ℝ^d,    u∈[-μ,μ],

with given μ>0, d = 2, 3,, and

    A := [0|e_1|e_2||e_d-1],   b := e_d,

where 0 denotes the d× 1 column vector of zeros, and e_i is the i-th basis (column) vector in ℝ^d for i=1,,d. Our intent in this paper is to study the geometry of the forward reach set ℛ(𝒳_0,t) for (<ref>) at time t, starting from a given compact convex set of initial conditions 𝒳_0⊂ℝ^d, i.e.,

    ℛ(𝒳_0,t) := {x(t)∈ℝ^d|ẋ =    Ax + bu,   x(0) ∈𝒳_0,
       u∈[-μ,μ]}.

In words, ℛ(𝒳_0,t) is the set of all states the controlled dynamics (<ref>) can reach at time t>0, starting from the set 𝒳_0 at t=0, with bounded control u(t)∈[-μ,μ]. Formally,

    ℛ(𝒳_0,t)   = exp(tA)𝒳_0∔∫_0^texp((t-τ)A)b[-μ,μ]τ
       = exp(tA)𝒳_0∔∫_0^texp(sA)b[-μ,μ] s,

where ∔ denotes the Minkowski sum, and the set-valued Aumann integral <cit.> above is defined as follows. For any point-to-set function F(·), we define 

    ∫_0^tF(s) s := lim_Δ↓ 0 ∑_i=0^⌊t/Δ⌋Δ F(iΔ),

where the summation symbol Σ stands for the Minkowski sum, and ⌊·⌋ is the floor operator; see e.g., <cit.>. We will often consider the special case of singleton initial set 𝒳_0≡{x_0}. 

It is straightforward to prove that ℛ(𝒳_0,t) is a compact convex subset of ℝ^d for all t>0. Notice however, that the (space-time) forward reachable tube 

    ℛ(𝒳_0,t) := ⋃_0≤τ≤ tℛ(𝒳_0,τ),

need not be convex in ℝ^d×ℝ_>0. Fig. <ref> illustrates this for the double integrator (i.e., d=2 case) with 𝒳_0≡{x_0}.

Our motivation behind studying the geometry of the integrator reach sets is twofold. 

First, integrators are simple prototypical linear time invariant (LTI) systems that feature prominently in the systems-control literature on reach set computation (see e.g., <cit.>, <cit.>,<cit.>). Despite their ubiquity and pedagogical importance, very little is known about the specific geometry of the integrator reach sets. Existing results come in two flavors: rather generic statements (e.g., that these sets are compact and convex), and specific approximation algorithms (e.g., ellipsoidal <cit.> and zonotopic <cit.> inner and outer-approximation). To minimize conservatism in numerically approximating the true reach set while preserving safety, one often considers minimum  volume outer-approximation via specific algorithms, see e.g., <cit.>. In such context, not knowing the volume or diameter of the true reach set hinders a quantitative assessment of whether one algorithm is better than other, in terms of approximating the true reach set. Consequently, one has to content with graphical or statistical assessments about the quality of approximation.      

Second, many nonlinear control systems of practical interest, such as aerial and ground vehicles are differentially flat <cit.>, meaning they can be put in a chain of integrator (i.e., Brunovsky canonical) form via a nonlinear change of coordinates. Thus, having an analytical handle on the integrator reach set (in feedback linearized coordinates, see <cit.>) can help compute or approximate the reach set in the original state space. 

In this paper, we present basic convex geometry of the integrator reach sets in finite dimensions with bounded control, and derive closed-form expressions for the volume and the diameter of the same. From the authors' perspective, this paper makes fundamental systems-theoretic (not algorithmic) contribution. Our hope is that the ensuing development will be useful to systems-control researchers using reach set as a construct in applications such as motion planning, and will provide the foundation for development and benchmarking of algorithms.

This paper is structured as follows. Section <ref> provides a brief review of the calculus of support functions, and deduces the support function for the integrator reach set. In Section <ref>, a closed-form formula for the volume of the integrator reach set is derived. Along the way, we establish that the said reach set is a zonoid. In Section <ref>, we provide a closed-form formula for the diameter of the integrator reach set. Section <ref> concludes the paper.

 










§ SUPPORT FUNCTION CALCULUS



 §.§ Preliminaries

A basic descriptor of a compact convex set 𝒦⊂ℝ^d, is its support function h_𝒦(·) given by

    h_𝒦(y) := ∈𝒦sup {⟨,⟩|y∈ℝ^d},

where ⟨·,·⟩ denotes the standard Euclidean inner product. Geometrically, h_𝒦(y) gives the signed distance of the supporting hyperplane of 𝒦 with outer normal vector y, measured from the origin. Since a compact convex set 𝒦 is the intersection of its supporting halfspaces, the function h_𝒦(·) characterizes 𝒦 by specifying the location of its supporting hyperplanes, parameterized by their outer normal vectors y∈ℝ^d. A different way to view this characterization is the following <cit.>: h_𝒦(·) is the Legendre-Fenchel conjugate of the indicator function of the set 𝒦.

Several properties of the support function are well-known:
(i) h_𝒦 is a convex function of y∈ℝ^d, and its epigraph is a convex cone.

(ii) h_𝒦 is positive homogeneous, i.e., h_𝒦(α)=α h_𝒦() for α>0; also, h_𝒦 is sub-additive, i.e., h_𝒦( + z) ≤ h_𝒦() + h_𝒦(z) for all ,z∈ℝ^d.

(iii) For 𝒦_1,𝒦_2 compact convex, 𝒦_1⊆𝒦_2 if and only if h_𝒦_1() ≤ h_𝒦_2() for all ∈ℝ^d.

(iv) For M∈ℝ^d× d and m,∈ℝ^d, h_M𝒦+m() = ⟨,m⟩ + h_𝒦(M^⊤).

(v) For 𝒦_1,𝒦_2,,𝒦_r compact convex, and for all ∈ℝ^d,

    h_𝒦_1∔∔𝒦_r() = h_𝒦_1() +  + h_𝒦_r(),

 
    h_ConvexHull(𝒦_1∪∪𝒦_r)() = max{h_𝒦_1 (), ,  h_𝒦_r()},
 
 
    h_𝒦_1∩∩𝒦_r() = _1 +  + _r =inf{h_𝒦_1(_1) +  + h_𝒦_r(_r)}.

 
Due to property (ii), a compact convex set in ℝ^d is uniquely determined by its support function restricted to the unit sphere 𝕊^d-1. We will also need the following result that builds on Lemma <ref> in Appendix <ref>.

(Support function of the integral of a set-valued function) Let F(s) be a point-to-set function, and denote its support function as h_F(s)(y) ≡ h(s,y) for any y∈ℝ^d. Then,

    h_∫_0^tF(s) s(y) = ∫_0^t h(s,y) s.
	



For any y∈ℝ^d, we have

    h_∫_0^tF(s) s(y)    (<ref>)= h_lim_Δ↓ 0 ∑_i=0^⌊t/Δ⌋Δ F(iΔ)(y)
       = ∈lim_Δ↓ 0 ∑_i=0^⌊t/Δ⌋Δ F(iΔ)sup⟨y,⟩
       (Lemma <ref>)=lim_Δ↓ 0∈∑_i=0^⌊t/Δ⌋Δ F(iΔ)sup⟨y,⟩
       = lim_Δ↓ 0h_∑_i=0^⌊t/Δ⌋Δ F(iΔ)(y)
       = lim_Δ↓ 0∑_i=0^⌊t/Δ⌋Δ h(iΔ,y)	
       = ∫_0^t h(s,y) s,

wherein the last but one line used the properties (iv)-(v) for the support function.	


A special case of the above result for continuous-time LTI systems was derived in <cit.>. Compared to the same, both the statement and proof of Proposition <ref> are general (valid for any point-to-set function).
 

In the following, we will derive the support function of the set (<ref>), and show how geometric quantities of interest can be derived from the same.



 §.§ Support Function of the Integrator Reach Set

From (<ref>) and the properties (iv)-(v) in Section <ref>, 

    h_ℛ(𝒳_0,t)() = h_𝒳_0(exp(tA^⊤)) + h_∫_0^texp(sA)b[-μ,μ] s().

Using Proposition <ref> and property (iv), we simplify (<ref>) as

    h_ℛ(𝒳_0,t)() =    h_𝒳_0(exp(tA^⊤)) 
       +∫_0^t h_b[-μ,μ](exp(sA^⊤)) s.

Noting the structure of the state transition matrix from Appendix <ref> (equation (<ref>)), and that

    h_b[-μ,μ]() = u∈[-μ,μ]sup⟨,bu⟩ = μ|⟨,b⟩|,
 
we can rewrite (<ref>) as 

    h_ℛ(𝒳_0,t)() =   _0∈𝒳_0sup⟨,exp(tA)_0⟩ + μ∫_0^t|⟨,ξ(s)⟩|  s,

where ξ(s) is the last column of the matrix exp(sA), i.e.,

    ξ(s) := [ s^d-1/(d-1)! s^d-2/(d-2)!                         s            1 ]^⊤.

Expressions (<ref>)-(<ref>) describe the support function of the integrator reach set. 



§ FUNCTIONALS OF THE INTEGRATOR REACH SET

We now show how the ideas presented thus far can be used to compute two functionals of the reach set that are of practical interest, viz. the volume, and the diameter or maximal width of the set. Both these functionals measure the “size" of the reach set. 



 §.§ Volume

We denote the (d-dimensional) volume of the integrator reach set in d-dimensions, as (ℛ(𝒳_0,t)). It can be written in terms of the support function:

    (ℛ(𝒳_0,t)) = 1d∫_𝕊^d-1h_ℛ(𝒳_0,t)(η)  S_ℛ(𝒳_0,t)(η),

where η∈𝕊^d-1 (the Euclidean unit sphere imbedded in ℝ^d), and S_ℛ(𝒳_0,t) denotes the differential of the surface area measure on ℛ(𝒳_0,t). Let S be the surface area measure on 𝕊^d-1. Then, we can rewrite (<ref>) as (see e.g., <cit.>)

    (ℛ(𝒳_0,t)) = 1d∫_𝕊^d-1h_ℛ(𝒳_0,t)(η) S_ℛ(𝒳_0,t) S(η)  S(η),

where the Radon-Nikodym derivative S_ℛ/ S : 𝕊^d-1↦ℝ. However, computing (<ref>) with (<ref>) seems unwieldy as we lack analytical handle on the surface measure of the integrator reach set.

To pursue an alternative strategy for volume computation, we uniformly discretize the interval [0,t] into n subintervals

    [(i-1)t/n, it/n),    i=1, 2, , n,

with (n+1) breakpoints {t_i}_i=0^n, where t_i:=it/n for i=0,1,,n. We also consider singleton 𝒳_0≡{_0}. Then, from (<ref>), we have

    (ℛ({_0},t))    = (∫_0^texp(sA)b[-μ,μ] s)
       = (lim_n→∞∑_i=0^nt/nexp(t_iA)b[-μ,μ]),

where the last line used the definition of the set-valued integral (<ref>), and that each subinterval is of length t/n. We simplify the above expression by taking the scaling factor μ t/n outside the Minkowski sum, interchanging the limit and  (via Lemma <ref>), and using the homogeneity of the (·) operator, to obtain

    (ℛ({_0},t)) = lim_n→∞(μ tn)^d(∑_i=0^nexp(t_iA)b[-1,1]).

At this point, we notice that the set

    ∑_i=0^nexp(t_iA)b[-1,1]

is a Minkowski sum of n+1 intervals, each interval being rotated and scaled in ℝ^d via different linear transformations exp(t_iA), i=0,1,,n. To proceed further, we recall few facts about zonotopes <cit.>.



  §.§.§ Zonotopes and zonoids

A d-dimensional zonotope 𝒵_n is defined as a Minkowski sum of n line segments:

    𝒵_n:= {∑_j=1^nγ_jv_j|γ_j∈[-1,1], v_j∈ℝ^d, j=1,,n},

where the vectors {v_j}_j=1^n are called the “generators" of 𝒵_n. To make this explicit, one often writes 

    𝒵_n≡𝒵_n({v_j}_j=1^n) ⊂ℝ^d.
 
Equivalently, (<ref>) can be seen as an affine transformation of the unit cube in ℝ^d. From Section <ref>, the support function of (<ref>) is 

    h_𝒵_n(y) = ∑_j=1^n|⟨y,v_j⟩|,   y∈ℝ^d.

Conversely, a set 𝒵_n with support function of the form (<ref>) must be a zonotope <cit.>. See <cit.> for a support function inequality characterization of zonotopes. The limiting (where the limit is w.r.t. the Hausdorff metric, see Appendix <ref>) compact convex set 𝒵_∞:= lim_n→∞𝒵_n is termed as the “zonoid" <cit.>.

The following formula for the d-dimensional volume of (<ref>) appears in <cit.>, who attributes it to <cit.>:

    (𝒵_n) = 2^d∑_1 ≤ j_1 < j_2 <  < j_d≤ n|(v_j_1|v_j_2||v_j_d) |,

where the summands are (non-negative) determinants of the d× d matrices, as shown. The formula (<ref>) also appears in <cit.>, and can be derived by decomposing 𝒵_n into parallelopipeds <cit.>, whose volumes are given by the summand determinants.

In our context, the aforesaid facts have two immediate consequences, summarized below.

(i) Recall that 

    ξ(t_i) = ξ(it/n) ∈ℝ^d,   i=0,1,,n,
 
where ξ(·) is given by (<ref>). The set (<ref>) is a zonotope 𝒵_n+1({ξ(t_i)}_i=0^n)	 with support function

    h_𝒵_n+1({ξ(t_i)}_i=0^n)(y) = ∑_i=0^n|⟨y,ξ(t_i)⟩|,   y∈ℝ^d.

(ii) The limiting compact convex set ∫_0^texp(sA)b[-1,1] s is a zonoid.





  §.§.§ Back to volume computation

Thanks to Proposition <ref>, we can use (<ref>) to rewrite the right-hand-side (RHS) of (<ref>) as

    (2μ t)^dlim_n→∞1n^d∑_0 ≤ i_1 < i_2 <  < i_d≤ n|(ξ(t_i_1) |ξ(t_i_2) ||ξ(t_i_d)) |.

This leads to the following result (proof in Appendix <ref>).
 
(Volume of the integrator reach set)
Given controlled dynamics (<ref>)-(<ref>), and a fixed x_0∈ℝ^d, let 𝒳_0≡{x_0}. At time t>0, the volume of the reach set (<ref>) is

    (ℛ({_0},t)) = (2μ)^dt^d(d+1)/2∏_k=1^d-1k!lim_n→∞1/n^d(d+1)/2×
    ∑_0 ≤ i_1 < i_2 <  < i_d≤ n  ∏_1 ≤α < β≤ d(i_β - i_α).
	



Since the sum

    ∑_0 ≤ i_1 < i_2 <  < i_d≤ n  ∏_1 ≤α < β≤ d(i_β - i_α)

must return a polynomial in n of degree d(d+1)/2, hence the limit in (<ref>) will simply extract the leading coefficient of this polynomial, i.e., the coefficient of n^d(d+1)/2. A corollary is that the said limit (which is a function of d) is well defined.	




If the set of initial conditions 𝒳_0 is not singleton, then computing the volume of the reach set requires computing volume of a Minkowski sum: (ℛ(𝒳_0,t)) = (ℛ_0∔ℛ_t), where ℛ_0:=exp(tA)𝒳_0, and ℛ_t := ∫_0^texp(sA)b[-μ,μ] s. 




To illustrate the use of (<ref>), consider d=2, i.e., the case of a double integrator for which the shape of the reach set is as in Fig. <ref>(a). From (<ref>), its area is

    4μ^2t^3lim_n→∞1/n^3∑_i=0^n∑_j=i+1^n(j-i),

wherein we renamed the indices (i_1,i_2)↦(i,j). Straightforward calculation gives

    ∑_i=0^n∑_j=i+1^n(j-i) = 1/6n(n+1)(n+2);
 
thus the limit in (<ref>) evaluates to 1/6, and hence the area equals 2μ^2t^3/3. We note that for the double integrator, it is possible to derive the area formula 2μ^2t^3/3 by first deriving the equations of the bounding curves <cit.> (red and blue curves in Fig. <ref>(a)), and then computing the area enclosed by the two <cit.>. However, it is difficult to generalize this approach to higher dimensions.  

As another example, consider d=3 (the triple integrator). Then (<ref>) reduces to

    4μ^3t^6lim_n→∞1/n^6∑_i=0^n∑_j=i+1^n∑_k=j+1^n(k-j)(k-i)(j-i),

where again we renamed the indices (i_1,i_2,i_3)↦(i,j,k). Noting that 

    ∑_i=0^n∑_j=i+1^n∑_k=j+1^n(k-j)(j-i)(k-i) 
    
    = 1/180(n-1)n(n+1)^2(n+2)(n+3),

we find that the limit in (<ref>) evaluates to 1/180, and therefore, the volume of the triple integrator reach set is μ^3t^6/45.

Similar calculation shows that the (4-dimensional) volume of the quadruple integrator (i.e., d=4) is μ^4t^10/18900. 





 §.§ Width

The width <cit.> of the reach set ℛ(𝒳_0,t) is 

    w_ℛ(𝒳_0,t)(η) := h_ℛ(𝒳_0,t)(η) + h_ℛ(𝒳_0,t)(-η),

where η∈𝕊^d-1, and h_ℛ(𝒳_0,t)(·) is given by (<ref>). That is, (<ref>) gives the width of the reach set in the direction η. 

For 𝒳_0≡{x_0} (a singleton set), combining (<ref>) and (<ref>), we have

    w_ℛ({x_0},t)(η)    = μ∫_0^t{|⟨η,ξ(s)⟩| + |⟨-η,ξ(s)⟩|}  s 
       = 2μ∫_0^t|⟨η,ξ(s)⟩|  s,

where the last equality follows from the fact that ξ(s) in (<ref>) is component-wise non-negative for all 0 ≤ s ≤ t. Fig. <ref> shows how the width of the integrator reach set for d=2 varies over θ∈𝕊^1 (i.e., η≡ (cosθ, sinθ)^⊤ in this case).  





The diameter of the reach set is the maximal width:

    diam(ℛ(𝒳_0,t)) := η∈𝕊^d-1max w_ℛ(𝒳_0,t)(η).

It is clear from the support function property (ii) in Section <ref> that both the width and the diameter are Minkowski sub-additive, i.e., w_𝒦_1∔𝒦_2(·) ≤ w_𝒦_1(·) + w_𝒦_2(·), and diam(𝒦_1∔𝒦_2) ≤diam(𝒦_1) + diam(𝒦_2) for compact convex 𝒦_1,𝒦_2.


Notice that the integrand in (<ref>) is a convex function in η for each s∈[0,t], and therefore w_ℛ({x_0},t)(η) is convex in η; see <cit.>. So, computing (<ref>) is a concave problem:

    2μ η^⊤η=1max ∫_0^t|⟨η,ξ(s)⟩|  s.

We have the following result (proof in Appendix <ref>).

(Diameter of the integrator reach set)
Given controlled dynamics (<ref>)-(<ref>), and a fixed x_0∈ℝ^d, let 𝒳_0≡{x_0}, and the vector ζ(t) := ∫_0^tξ(s) s. At time t>0, the diameter (i.e., maximal width) of the reach set (<ref>) is


    diam(ℛ({_0},t))    = 2μ∥ζ(t) ∥_2
       = 2μ{∑_j=1^d(t^jj!)^2}^1/2.

		
		

To illustrate Theorem <ref>, consider again the double integrator for which η≡ (cosθ, sinθ)^⊤, θ∈𝕊^1, and (<ref>) becomes

    2μ θ∈[0,2π)max ∫_0^t| scosθ + sinθ|  s.

In this case, ζ(t) = (t^2/2, t)^⊤, and from (<ref>) in Appendix <ref>, we obtain the maximizers

    [ cosθ^max; sinθ^max ]= [ t^2/2√(t^4/4 + t^2);     t√(t^4/4 + t^2) ]⇒θ_r^max = rπ + arctan(2/t),

for r=0,1 (so as to make θ∈[0,2π)). In Fig. <ref>, the location of these maximizers in the horizontal axis are depicted via dashed vertical lines. From (<ref>), the diameter of the double integrator reach set becomes μ t √(t^2 + 4), which for our choice of parameters in Fig. <ref>, equals 89.4427.

Similarly, the diameter of the triple integrator (d=3) reach set, from (<ref>), equals (μ t/3)√(t^4 + 9 t^2 + 36).







§ CONCLUSIONS

In this paper, we took a close look at the convex geometry of the integrator reach sets. Using support function calculus, we established that the integrator reach set is a zonoid – a limiting compact convex set of a sequence of zonotopes (Minkowski sum of line segments). This limit is defined in the (two-sided) Hausdorff metric. These ideas enabled us to derive closed-form formula for the volume and diameter of the integrator reach sets. Several examples are given to elucidate the results.






§ ACKNOWLEDGMENTS

This research was partially supported by Chancellor's Fellowship from the University of California, Santa Cruz.








 §.§ Integrator State Transition Matrix

The state matrix A for (<ref>) is the upper shift matrix, and hence the state transition matrix exp(tA) is upper triangular with all ones in the diagonal, as given below.

For the d× d matrix A as in (<ref>), we have

    exp(tA)_i,j = t^j-i/(j-i)!   for   i<j,
    
     	1    for   i=j,
    
     	0    for   i>j,

where the indices i,j=1,,d. 	


Since A is nilpotent with order d (i.e., A^d is zero matrix), hence exp(tA) = ∑_j=0^d-1(tA)^jj!, from which the result follows.	





 §.§ Convergence of Compact Convex Sets

Let {𝒦_i}_i∈ℕ be a sequence of compact convex sets in ℝ^n. Define the two-sided Hausdorff distance δ_H (which is a metric) between any two non-empty sets 𝒫,𝒬⊆ℝ^d as

    δ_H(𝒫,𝒬) := max{p∈𝒫sup q∈𝒬inf∥p - q∥_2,
    q∈𝒬sup p∈𝒫inf∥p - q∥_2}.

For 𝒫,𝒬 compact and convex, (<ref>) becomes

    δ_H(𝒫,𝒬) = η∈𝕊^d-1sup | h_𝒫(η) - h_𝒬(η)|,

where 𝕊^d-1 denotes the Euclidean unit sphere imbedded in ℝ^d. The sequence {𝒦_i}_i∈ℕ converges to a compact convex set 𝒦 (loosely denoted as 𝒦_i→𝒦) iff δ_H(𝒦_i,𝒦) → 0 as i→∞. In fact, the collection of all compact convex sets equipped with the metric δ_H constitutes a complete[i.e., every Cauchy sequence of sets is convergent in δ_H, and vice versa.] metric space. The following Lemma will be useful in proving Proposition <ref> in Section <ref>.

Let {𝒦_i}_i∈ℕ be a sequence of compact convex sets in ℝ^n. Then, 𝒦_i→𝒦 ⇔ h_𝒦_i(·) → h_𝒦(·).	


We know that 𝒦_i→𝒦 iff δ_H(𝒦_i,𝒦)→ 0. From (<ref>), the latter is equivalent to h_𝒦_i(·) → h_𝒦(·).	

We will also need the following.

Let {𝒦_i}_i∈ℕ be a sequence of compact convex sets in ℝ^d. Let (·) denote the d-dimensional volume. If 𝒦_i→𝒦, then (𝒦_i) →(𝒦) as i→∞.	


Follows from continuity of the volume functional <cit.>, and uniform convergence of the support functions of corresponding sets.






 §.§ Proof of Theorem <ref>


For a given d-tuple {i_1, i_2, , i_d}, where 0 ≤ i_1 < i_2 < , < i_d≤ n, let 

    Δ(i_1,i_2,,i_d) := (ξ(t_i_1) |ξ(t_i_2) ||ξ(t_i_d))
 
denote the corresponding summand determinant in (<ref>). In the matrix list notation, let us use the vertical bars |·| to mean the absolute value of the determinant. From (<ref>), Δ(i_1,i_2,,i_d) equals

    (i_1t/n)^d-1(d-1)!   (i_2t/n)^d-1(d-1)!      (i_dt/n)^d-1(d-1)!
             
    (i_1t/n)^d-2(d-2)!   (i_2t/n)^d-2(d-2)!      (i_dt/n)^d-2(d-2)!
             
    ⋮   ⋮   ⋮   ⋮
             
    
     i_1t/n     i_2t/n        i_dt/n
             
    
     1     1        1
     
       = (t/n)^1 + 2 +  + (d-1)1!×2!××(d-1)! 
    i_1^d-1    i_2^d-1       i_d^d-1
             
    
     i_1^d-2    i_2^d-2       i_d^d-2
             
    ⋮   ⋮   ⋮   ⋮
             
    
     i_1    i_2       i_d
             
    
     1     1        1
     , 
       =  (t/n)^d(d-1)/2∏_k=1^d-1k!
     1     1        1
             
    
       i_1    i_2       i_d
             
    ⋮   ⋮   ⋮   ⋮
             
      
     i_1^d-2    i_2^d-2       i_d^d-2
             
    
    i_1^d-1    i_2^d-1       i_d^d-1
    ,

wherein the last but one step brought the multiple for each row outside the determinant, and the last step rearranged the rows (without affecting sign since we are dealing with the absolute value of the determinant). 

Next, notice that the determinant in (<ref>) is the well-known Vandermonde determinant that equals <cit.>

    ∏_1 ≤α < β≤ d(i_β - i_α).

Combining (<ref>), (<ref>) and (<ref>), we arrive at (<ref>).






 §.§ Proof of Theorem <ref>


Let ξ_i(s) denote the i-th component of the vector ξ(s) given by (<ref>), where i=1,2,,d. We notice that |∑_i=1^dη_iξ_i(s)|≤∑_i=1^d|η_iξ_i(s)| = ∑_i=1^d|η_i|ξ_i(s) (since the vector ξ(s) is elementwise nonnegative) for any s∈[0,t]. Therefore, 	

    ∫_0^t|∑_i=1^dη_iξ_i(s)|  s ≤∑_i=1^d|η_i|∫_0^tξ_i(s)  s = ∑_i=1^dζ_i(t)|η_i|.

By standard Lagrange multiplier argument, maximizing the weighted ℓ_1-norm ∑_i=1^dζ_i(t)|η_i| appearing in the RHS of (<ref>) w.r.t. η, subject to η^⊤η=1, yields the maximizer

    η^max = ±ζ(t)∥ζ(t)∥_2,

i.e., the unit vector associated with ζ(t) upto plus-minus sign permutations among its components.

Substituting η^max from (<ref>) back in (<ref>) yields the maximal value attainable by the integral in (<ref>) as ∥ζ(t)∥_2. We thus obtain

    diam(ℛ({_0},t)) = 2μ∥ζ(t) ∥_2,

which is indeed (<ref>). The expression (<ref>) results from recalling that the components of ζ(t), by definition, are

    ζ_i(t)  := ∫_0^tξ_i(s)  s = ∫_0^ts^d-i(d-i)!  s = t^d-i+1(d-i+1)!,

where i=1,2,,d. Therefore,

    ζ(t)_2 = (∑_j=1^d(t^j/j!)^2)^1/2,
 
and the proof is complete.







 









99

aumann1965integrals
R.J. Aumann, “Integrals of set-valued functions", Journal of Mathematical Analysis and Applications, Vol. 12, No. 1, pp. 1–12, 1965.

varaiya2000reach
P. Varaiya, “Reach set computation using optimal control", in M.K. Inan, R.P. Kurshan (eds), Verification of Digital and Hybrid Systems, NATO ASI Series (Series F: Computer and Systems Sciences), Springer, Vol 170, pp. 323–331, 2000.

maksarov1996state
D.G. Maksarov, and J.P. Norton, “State bounding with ellipsoidal set description of the uncertainty", International Journal of Control, Vol. 65, no. 5, pp. 847–866, 1996. 

KurzhanskiValyiBook
A.B. Kurzhanski, and I. Vályi, Ellipsoidal Calculus for Estimation and Control, Systems and Control: Foundations and Applications, Birkhäuser, Boston, and the International Institute for Applied Systems Analysis, 1997.


varaiyabook
A.B. Kurzhanski, and P. Varaiya, Dynamics and Control of Trajectory Tubes. Springer International Publishing, Switzerland, 2014.

<https://tinyurl.com/yxesbk8k> 

fainekos2009temporal
G.E. Fainekos, A. Girard, H. Kress-Gazit, and G.J. Pappas, “Temporal logic motion planning for dynamic robots", Automatica, Vol. 45, No. 2, pp. 343–352, 2009. 

durieu2001multi
C. Durieu, E. Walter, and B. Polyak, “Multi-input multi-output ellipsoidal state bounding", Journal of Optimization Theory and Applications, Vol. 111, No. 2, pp. 273–303, 2001.




althoff2007reachability
M. Althoff, O. Stursberg, and M. Buss, “Reachability analysis of linear systems with uncertain parameters and inputs", Proceedings of the 46th IEEE Conference on Decision and Control (CDC), pp. 726–732, 2007. 


halder2018parameterized
A. Halder, “On the parameterized computation of minimum volume outer ellipsoid of Minkowski sum of ellipsoids", Proceedings of the IEEE Conference on Decision and Control (CDC), pp. 4040–4045, 2018. 

halder2018smallest
A. Halder, “Smallest ellipsoid containing p-sum of ellipsoids with application to reachability analysis", arXiv preprint arXiv:1806.07621, 2018.

<https://arxiv.org/pdf/1806.07621.pdf>


fliess1995flatness
M. Fliess, J. Lévine, P. Martin, and P. Rouchon, “Flatness and defect of non-linear systems: introductory theory and examples", International Journal of Control, Vol. 61, No. 6, pp. 1327–1361, 1995.

murray1995
R.M. Murray, M. Rathinam, andd W. Sluis, “Differential flatness of mechanical control systems: a catalog of prototype systems", in ASME International Mechanical Engineering Congress and Exposition, 1995.

fliess1999lie
M. Fliess, J. Lévine, P. Martin, and P. Rouchon, “A Lie-Bäcklund approach to equivalence and flatness of nonlinear systems", IEEE Transactions on Automatic Control, Vol. 44, No. 5, pp. 922-937, 1999.

nieuwstadt1998differential 
M. Van Nieuwstadt, M. Rathinam, and R.M. Murray, “Differential flatness and absolute equivalence of nonlinear control systems", SIAM Journal on Control and Optimization, Vol. 36, No. 4, pp. 1225-1239, 1998.



witsenhausen1968
H.S. Witsenhausen, “Sets of possible states of linear systems given
perturbed observations", IEEE Transactions on Automatic Control, Vol. 13, No. 5, pp. 556–558, 1968. 

guernic2010reachability
C. Le Guernic, and A. Girard, “Reachability analysis of linear systems using support functions", Nonlinear Analysis: Hybrid Systems, Vol. 4, No. 2, pp. 250–262, 2010.






rockafeller1970convex
R.T. Rockafeller, Convex Analysis, Princeton Landmarks in Mathematics, Princeton University Press, 1970.


girard2008efficient
A. Girard, and C. Le Guernic, “Efficient reachability analysis of linear systems using support functions", IFAC Proceedings, Vol. 41, No. 2, pp. 8966–8971, 2008.





lutwak1993the
E. Lutwak, “The Brunn-Minkowski-Firey theory I: mixed volumes and the Minkowski problem", Journal of Differential Geometry
, Vol. 38, No. 1, pp. 131–150, 1993.

schneider2014book
R. Schneider, Convex Bodies: the Brunn-Minkowski Theory, Encyclopedia of Mathematics and Its Applications, No. 151, Cambridge University Press, 2014.

boydbook
S. Boyd, and L. Vanderberghe, Convex Optimization, Cambridge University Press, 2004.






bolker1969class
E.D. Bolker, “A class of convex bodies", Transactions of the American Mathematical Society, Vol. 145, pp. 323–345, 1969.

mcmullen1971on
P. McMullen, “On zonotopes", Transactions of the American Mathematical Society, Vol. 159, 1971.

shephard1974combinatorial
G.C. Shephard, “Combinatorial properties of associated zonotopes", Canadian Journal of Mathematics, Vol. 26, no. 2, pp. 302–321, 1974. 

schneider1983zonoids
R.Schneider, and W. Weil, “Zonoids and related topics", in Convexity and its Applications, pp. 296–317, 1983.

witsenhausen1978support
H.S. Witsenhausen, “A support characterization of zonotopes", Mathematika, Vol. 25, No. 1, pp. 13–16, 1978.

ziegler2012lectures
G.M. Ziegler, Lectures on Polytopes, Vol. 152, Springer Science & Business Media, 2012. 


gianfortone2018thesis
L.M. Gianfortone, Ellipsoidal Algorithm for Fast Computation of Reachable Tubes, MS Thesis in Scientific Computing and Applied Mathematics, University of California, Santa Cruz, 2018.

<https://escholarship.org/uc/item/67p1s5fv>

hornjohnson2012
R.A. Horn, and C.R. Johnson, Matrix Analysis, Cambridge University Press, 2nd ed., 2012.










































