Raluca M Balan

Adam Jakubowski

Sana Louhichi

Functional Convergence of Linear Processes with Heavy-Tailed Innovations *

Keywords: limit theorems, functional convergence, stable processes, linear processes. MSC2000: 60F17, 60G52

, by proving that in the general setting partial sums of linear processes are convergent on the Skorokhod space equipped with the S topology, introduced by Jakubowski (1997).

Introduction and announcement of results

Let {Y j } j∈Z be a sequence of independent and identically distributed random variables. By a linear process built on innovations {Y j } we mean a stochastic process

X i = j∈Z c j Y i-j , i ∈ Z, (1)
where the constants {c j } j∈Z are such that the above series is P-a.s. convergent. Clearly, in non-trivial cases such a process is dependent, stationary and due to the simple linear structure many of its distributional characteristics can be easily computed (provided they exist). This refers not only to the expectation or the covariances, but also to more involved quantities, like constants for regularly varying tails (see e.g. [START_REF] Mikosch | The Supremum of a Negative Drift Random Walk with Dependent Heavy-Tailed Steps[END_REF] for discussion) or mixing coefficients (see e.g. [START_REF] Doukhan | Mixing: properties and examples[END_REF] for discussion).

There exists a huge literature devoted to applications of linear processes in statistical analysis and modeling of time series. We refer to the popular textbook [START_REF] Brockwell | Introduction to Time Series and Forecasting[END_REF] as an excellent introduction to the topic.

Here we would like to stress only two particular features of linear processes.

First, linear processes provide a natural illustration for phenomena of local (or weak) dependence and long-range dependence. The most striking results go back to Davydov ([9]), who obtained a rescaled fractional Brownian motion as a functional weak limit for suitable normalized partial sums of {X i }'s.

Another important property of linear processes is the propagation of big values. Suppose that some random variable Y j 0 takes a big value, then this big value is propagated along the sequence X i (everywhere, where Y j 0 is taken with a big coefficient c i-j 0 ). Thus linear processes form the simplest model for phenomena of clustering of big values, what is important in models of insurance (see e.g. [START_REF] Mikosch | The Supremum of a Negative Drift Random Walk with Dependent Heavy-Tailed Steps[END_REF]).

In the present paper we shall deal with heavy-tailed innovations. More precisely, we shall assume that the law of Y i belongs to the domain of strict attraction of a non-degenerate strictly α-stable law µ α , i.e.

Z n = 1 a n n i=1 Y i -→ D Z, (2)
where Z ∼ µ α . Let us observe that by the Skorokhod theorem ( [START_REF] Skorokhod | Limit theorems for stochastic processes with independent increments[END_REF]) we also have

Z n (t) = 1 a n [nt] i=1 Y i -→ D Z(t), (3)
where {Z(t)} is the stable Lévy process with Z(1) ∼ µ α , and the convergence holds on the Skorokhod space D([0, 1]), equipped with the Skorokhod J 1 topology.

Recall, that if the variance of Z is infinite, then (2) implies the existence of α ∈ (0, 2) such that

P(|Y j | > x) = x -α h(x), x > 0, ( 4
)
where h is a function that varies slowly at x = +∞, and also lim x→∞ P(Y j > x) P(|Y j | > x) = p and lim x→∞ P(Y j < -x) P(|Y j | > x) = q, p + q = 1.

(

) 5
The norming constants a n in (3) must satisfy

nP(|Y j | > a n ) = nh(a n ) a α n → C > 0, (6)
hence are necessarily of the form a n = n 1/α g(n 1/α ), where the slowly varying function g(x) is the de Bruijn conjugate of C/h(x) 1/α (see [START_REF] Bingham | Regular Variation Encyclopedia Math[END_REF]). Moreover, if α > 1, then EY j = 0 and if α = 1, then p = q in (5). Conversely, conditions (4), [START_REF] Bingham | Regular Variation Encyclopedia Math[END_REF] and

E Y j = 0, if α > 1, (7)
{Y j } are symmetric, if α = 1, (8)
imply [START_REF] Basrak | A functional limit theorem for partial sums of dependent random variables with infinite variance[END_REF]. If a n is chosen to satisfy [START_REF] Brockwell | Introduction to Time Series and Forecasting[END_REF] with C = 1, then µ α is given by the characteristic function

μ(θ) =          exp R 1 (e iθx -1)f α,p,q (x) dx if 0 < α < 1, exp R 1 (e iθx -1)f 1,1/2,1/2 (x) dx if α = 1, exp R 1 (e iθx -1 -iθx)f α,p,q (x) dx if 1 < α < 2, (9)
where f α,p,q (x) = p I(x > 0) + q I(x < 0) α|x| -(1+α) .

We refer to [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF] or any of contemporary monographs on limit theorems for the above basic information. Suppose that the tails of |Y j | are regularly varying, i.e. (4) holds for some α ∈ (0, 2), and the (usual) regularity conditions [START_REF] Bulinski | Limit Theorems for Associated Random Fields and Related Systems[END_REF] and [START_REF] Davis | Limit theory for moving averages of random variables with regularly varying tail probabilities[END_REF] are satisfied. It is an observation due to Astrauskas [START_REF] Astrauskas | Limit theorems for sums of linearly generated random variables[END_REF] (in fact: a direct consequence of the Kolmogorov Three Series Theorem -see Proposition 6.1 below) that the series (1) defining the linear process X i is P-a.s. convergent if, and only if,

j∈Z |c j | α h(|c j | -1 ) < +∞. ( 10
)
Given the above series is convergent we can define

S n (t) = 1 b n [nt] i=1 X i , t ≥ 0, ( 11
)
and it is natural to ask for convergence of S n 's, when b n is suitably chosen.

Astrauskas [START_REF] Astrauskas | Limit theorems for sums of linearly generated random variables[END_REF] and Kasahara & Maejima [START_REF] Kasahara | Weighted sums of i.i.d. random variables attracted to integrals of stable processes[END_REF] showed that fractional stable Lévy Motions can appear in the limit of S n (t)'s, and that some of the limiting processes can have regular or even continuous trajectories, while trajectories of other can be unbounded on every interval.

In the present paper we consider the important case of summable coefficients:

j∈Z |c j | < +∞. ( 12
)
In Section 2 we give necessary and sufficient conditions for the finite dimensional convergence

S n (t) = 1 a n [nt] i=1 X i -→ f.d.d. A • Z(t), (13)
where the constants a n are the same as in (2), A = j∈Z c j and {Z(t)} is an α-stable Lévy Motion such that Z(1) ∼ Z. The obtained conditions lead to tractable sufficient conditions, which in case α < 1 are new and essentially weaker than condition j∈Z |c j | β < +∞, for some 0 < β < α, considered in [START_REF] Astrauskas | Limit theorems for sums of linearly generated random variables[END_REF], [START_REF] Davis | Limit theory for moving averages of random variables with regularly varying tail probabilities[END_REF] and [START_REF] Kasahara | Weighted sums of i.i.d. random variables attracted to integrals of stable processes[END_REF]. See Section 4 for details. Notice that in the case A = 0 another normalization b n is possible with a non-degenerate limit. We refer to [START_REF] Paulauskas | On α-covariance, long, short and negative memories for sequences of random variables with infinite variance[END_REF] for comprehensive analysis of dependence structure of infinite variance processes. Section 3 contains strengthening of (13) to a functional convergence in some suitable topology on the Skorokhod space D([0, 1]). Since the paper [START_REF] Taqqu | Weak convergence of sums of moving averages in the α-stable domain of attraction[END_REF] it is known that in non-trivial cases (when at least two coefficients are non-zero) the convergence in the Skorokhod J 1 topology cannot hold. In fact none of Skorokhod's J 1 , J 2 , M 1 and M 2 topologies is applicable. This can be seen by analysis of the following simple example ( [START_REF] Taqqu | Weak convergence of sums of moving averages in the α-stable domain of attraction[END_REF], p. 488). Set

c 0 = 1, c 1 = -1 and c i = 0 if j = 0, 1. Then X i = Y i -Y i-1 and (13) holds with A = j c j = 0, i.e. S n (t) -→ P 0, t ≥ 0.
But we see that sup

t∈[0,1] S n (t) = max k≤n Y k -Y 0 /a n
converges in law to a Fréchet distribution. This means that supremum is not a continuous (or almost surely continuous) functional, what excludes convergence in Skorokhod's topologies in the general case.

For linear processes with nonnegative coefficients c i partial results were obtained by Avram and Taqqu [START_REF] Taqqu | Weak convergence of sums of moving averages in the α-stable domain of attraction[END_REF], where convergence in the M 1 topology was considered. Recently these results have been improved and developed in various directions in [START_REF] Louhichi | Functional convergence to stable Lévy motions for iterated random Lipschitz mappings[END_REF] and [START_REF] Basrak | A functional limit theorem for partial sums of dependent random variables with infinite variance[END_REF]. We use the linear structure of processes and the established convergence in the M 1 topology to show that in the general case, the finite dimensional convergence [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF] can be strengthen to convergence in the so-called S topology, introduced in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF]. This is a sequential and non-metric, but fully operational topology, for which addition is sequentially continuous.

Section 5 is devoted to some consequences of results obtained in previous sections. We provide examples of functionals continuous in the S topology. In particular we show that for every γ > 0

1 na γ n n k=1 k i=1 j c i-j Y j -AY i γ -→ P 0.
We also discuss possible extensions of the theory to linear sequences built on dependent summands. The Appendix contains technical results of independent interest.

Conventions and notations.

Throughout the paper, in order to avoid permanent repetition of standard assumptions and conditions we adopt the following conventions. We will say that {Y j }'s satisfy the usual conditions if they are independent identically distributed and (4), ( 5), ( 7) and ( 8) hold. When we write X i it is always the linear process given by (1) and is welldefined, i.e. satisfies [START_REF] Doukhan | Mixing: properties and examples[END_REF]. Similarly the norming constants {a n } are defined by [START_REF] Brockwell | Introduction to Time Series and Forecasting[END_REF] and the normalized partial sums S n (t) and Z n (t) are given by [START_REF] Esary | Association of random variables with applications[END_REF] with b n = a n and (3), respectively, where Z is the limit in (2) and Z(t) is the stable Lévy Motion such that Z(1) ∼ Z.

Convergence of finite dimensional distributions for summable coefficients

We begin with stating the main result of this section followed by its important consequence.

Theorem 2.1 Let {Y j } be an i.i.d. sequence satisfying the usual conditions. Suppose that

j |c j | < +∞. Then S n (t) = 1 a n [nt] i=1 X i -→ f.d.d. A • Z(t), where A = j c j ,
if, and only if,

0 j=-∞ d n,j α a α n h a n d n,j → 0, as n → ∞, ∞ j=n+1 d n,j α a α n h a n d n,j → 0, as n → ∞, (14)
where

d n,j = n-j k=1-j c k , n ∈ N, j ∈ Z.
Corollary 2.2 Under the assumptions of Theorem 2.1, define

U i = j |c i-j |Y j , X + i = j c + i-j Y j , X - i = j c - i-j Y j , (15)
where c + = c ∨ 0, c -= (-c) ∨ 0, c ∈ R 1 , and set

T n (t) = 1 a n [nt] i=1 U i , T + n (t) = 1 a n [nt] i=1 X + i , T - n (t) = 1 a n [nt] i=1 X - i . ( 16
)
Then T n (t) -→ f.d.d. A |•| • Z(t), where A |•| = j |c j |, implies T + n (t) -→ f.d.d. A + • Z(t), where A + = j c + j , T - n (t) -→ f.d.d. A -• Z(t), where A -= j c - j , S n (t) = T + n (t) -T - n (t) -→ f.d.d. A • Z(t), where A = j c j .
Proof of Corollary 2.2. In view of Theorem 2.1 it is enough to notice that

d n,j α a α n h a n d n,j = P n-j k=1-j c k • |Y j | > a n ≤ P n-j k=1-j |c k | • |Y j | > a n .
Proof of Theorem 2.1. Using Fubini's theorem, we obtain that

S n (t) = 1 a n [nt] i=1 j∈Z c i-j Y j = j∈Z 1 a n   [nt]-j k=1-j c k   Y j = j∈Z 1 a n d [nt],j Y j . (17)
Further, we may decompose

j∈Z 1 a n d [nt],j Y j = 0 j=-∞ 1 a n d [nt],j Y j + [nt] j=1 1 a n d [nt],j Y j + ∞ j=[nt]+1 1 a n d [nt],j Y j =S - n (t) + S 0 n (t) + S + n (t). (18)
Let us consider the partial sum process:

Z n (t) = 1 a n [nt] i=1 Y i , t ≥ 0.
First we will show Lemma 2.3 Under the assumptions of Theorem 2.1 we have for each t > 0

S 0 n (t) -A • Z n (t) -→ P 0. ( 19
)
In particular,

S 0 n (t) -→ D A • Z(t). ( 20
)
Proof of Lemma 2.3 Define

V 0 n = [nt] j=1 A -d [nt],j a n Y j = A • Z n (t) -S 0 n (t). ( 21
)
To prove that V 0 n -→ P 0 we apply Proposition 6.2. We have to show that

[nt] j=1 A -d [nt],j α a α n h a n A -d [nt],j = [nt] j=1 P A -d [nt],j • |Y j | > a n → 0, as n → ∞. (22) Since a n → ∞ and A -d [nt],j ≤ k∈Z |c k |, we have max 1≤j≤[nt] P A -d [nt],j • |Y j | > a n → 0. ( 23
)
We need a simple lemma.

Lemma 2.4 Let {a n,j ; 1 ≤ j ≤ n, n ∈ N} be an array of numbers such that max 1≤j≤n |a n,j | → 0, as n → ∞.

Then there exists a sequence j n → ∞,

j n = o(n), such that jn j=1 |a n,j | → 0. Proof of Lemma 2.4 For each m ∈ N there exists N m > max{N m-1 , m 2 } such that for n ≥ N m m j=1 |a n,j | < 1 m . Set j n = m, if N m ≤ n < N m+1 . By the very definition, if N m ≤ n < N m+1 then jn j=1 |a n,j | < 1 m and j n n ≤ j n N m = m N m ≤ m m 2 = 1 m .
By the above lemma and [START_REF] Peligrad | Central limit theorem for linear processes with infinite variance[END_REF] we can find a sequence j n → ∞, j n = o(n), increasing so slowly that still

jn j=1 P A -d [nt],j • |Y j | > a n + [nt] j=[nt]-jn+1 P A -d [nt],j • |Y j | > a n → 0.
For the remaining part we have max

jn<j≤[nt]-jn A -d [nt],j = max jn<j≤[nt]-jn A - [nt]-j k=1-j c k = δ n → 0, hence for δ ≥ δ n [nt]-jn j=jn+1 P A -d [nt],j • |Y j | > a n ≤ [nt]-jn j=jn+1 P |δ n ||Y j | > a n ≤ [nt] j=1 P |δ n ||Y j | > a n ≤ [nt] δ α a α n h(a n /δ) = [nt]δ α h(a n ) a α n h(a n /δ) h(a n ) . Since na -α n h(a n ) = nP(|Y | > a n ) → 1 and h varies slowly we have [nt]δ α h(a n ) a α n h(a n /δ) h(a n ) ∼ [nt]δ α 1 n → tδ α , as n → ∞.
But δ > 0 is arbitrary, hence we have proved [START_REF] Paulauskas | On α-covariance, long, short and negative memories for sequences of random variables with infinite variance[END_REF] and

V 0 n = A • Z n (t) -S 0 n (t) -→ P 0. Since A • Z n (t) -→ D A • Z(t),
Lemma 2.3 follows.

In the next step we shall prove Lemma 2.5 Under the assumptions of Theorem 2.1 the following items (i)-(iii) are equivalent.

(i)

S n (1) -→ D A • Z(1), (24)
(ii)

S - n (1) + S + n (1) -→ P 0. ( 25
) (iii) For every t ∈ [0, 1] S n (t) -A • Z n (t) -→ P 0. ( 26
)
Proof of Lemma 2.5 By Lemma 2.3 we know that S 0 n (1) 26) implies [START_REF] Skorokhod | Limit theorems for stochastic processes with independent increments[END_REF] and the latter implies [START_REF] Skorokhod | Limit theorems for stochastic processes[END_REF].

-A • Z n (1) -→ P 0 and S 0 n (1) -→ D A•Z(1). Since S n (1) = S - n (1)+ S 0 n (1)+ S + n (1), (
So let us assume [START_REF] Skorokhod | Limit theorems for stochastic processes[END_REF]. By regular variation of a n we have for each t ∈ (0, 1]

S n (t) = 1 a n [nt] i=1 X i = a [nt] a n 1 a [nt] [nt] i=1 X i -→ D t 1/α A • Z(1) ∼ A • Z(t). It follows that E e iθSn(t) = E e iθS 0 n (t) E e iθ S - n (t)+S + n (t) → E e iθA•Z(t) , θ ∈ R 1 .
Since also

E e iθS 0 n (t) → E e iθA•Z(t) , θ ∈ R 1 ,
and

E e iθA•Z(t) = 0, θ ∈ R 1 (for Z(t) has infinitely divisible law), we conclude that E e iθ S - n (t)+S + n (t) → 1, θ ∈ R 1 .
Thus S - n (t) + S + n (t) -→ P 0 and by Lemma 2.3 also S 0 n (t) -A • Z(t) -→ P 0. Hence [START_REF] Topsøe | A criterion for weak convergence of measures with an application to convergence of measures on D([0, 1])[END_REF] follows.

Let us observe that by Proposition 6.2 (25) holds if, and only if,

0 j=-∞ d n,j α a α n h a n d n,j + ∞ j=n+1 d n,j α a α n h a n d n,j → 0, as n → ∞, (27)
i.e. relation [START_REF] Jakubowski | The a.s. Skorohod representation for subsequences in nonmetric spaces[END_REF] holds. Therefore the proof of Theorem 2.1 will be complete, if we can show that convergence of one-dimensional distributions implies the finite dimensional convergence. But this is obvious in view of (26):

S n (t 1 ), S n (t 2 ), . . . , S n (t m ) -A • Z n (t 1 ), Z n (t 2 ), . . . , Z n (t m ) -→ P 0,
and the finite dimensional distributions of stochastic processes A • Z n (t) are convergent to those of A • Z(t).

Remark 2.6 Observe that for one-sided moving averages the two conditions in ( 14) reduce to one (the expression in the other equals 0). This is the reason we use in Theorem 2.1 two conditions replacing the single statement [START_REF] Tyran-Kamińska | Functional limit theorems for linear processes in the domain of attraction of stable laws[END_REF].

Remark 2.7 In the proof of Proposition 6.2 we used the Three Series Theorem with the level of truncation 1. It is well known that any r ∈ (0, +∞) can be chosen as the truncation level. Hence conditions ( 14) admit an equivalent reformulation in the "r-form"

0 j=-∞ d n,j α a α n h r • a n d n,j → 0, as n → ∞. ∞ j=n+1 d n,j α a α n h r • a n d n,j → 0, as n → ∞.
3 Functional convergence

Convergence in the M 1 topology

As outlined in Introduction (see also Section 5.2 below), the convergence of finite dimensional distributions of linear processes built on heavy-tailed innovations cannot be, in general, strengthened to functional convergence in any of Skorokhod's topologies J 1 , J 2 , M 1 , M 2 . The general linear process {X i } can be, however, represented as a difference of linear processes with non-negative coefficients. Let us recall the notation introduced in Corollary 2.2:

X + i = j c + i-j Y j , T + n (t) = 1 a n [nt] i=1 X + i , X - i = j c - i-j Y j , T - n (t) = 1 a n [nt] i=1 X - i .
Notice, that in general

X ± i (ω) is not equal to X i (ω)
± and that we have

S n (t) = T + n (t) -T - n (t). ( 28
)
The point is that both T + n (t) and T - n (t) are partial sums of associated sequences in the sense of [START_REF] Esary | Association of random variables with applications[END_REF] (see e.g. [START_REF] Bulinski | Limit Theorems for Associated Random Fields and Related Systems[END_REF] for the contemporary theory) and thus exhibit much more regularity.

Theorem 1 of Louhichi and Rio [START_REF] Louhichi | Functional convergence to stable Lévy motions for iterated random Lipschitz mappings[END_REF] can be specified to the case of linear processes considered in our paper in the following way. Proposition 3.1 Let the innovation sequence {Y j } satisfies the usual conditions. Let c j ≥ 0, j ∈ Z, and

j c j < +∞. ( 29
)
If the linear process {X i } is well-defined and

S n (t) -→ f.d.d. A • Z(t),
then also functionally

S n -→ D A • Z on the Skorokhod space D([0, 1]) equipped with the M 1 topology. Remark 3.2
The first result of this type was obtained by Avram and Taqqu [START_REF] Taqqu | Weak convergence of sums of moving averages in the α-stable domain of attraction[END_REF]. They required however more regularity on coefficients (e.g. monotonicity of {c j } j≥1 and {c -j } j≥1 ).

M 1 -convergence implies S-convergence

Let us turn to linear processes with coefficients of arbitrary sign. Given decomposition [START_REF] Whitt | Stochastic-Process Limits. An Introduction to Stochastic-Process Limits and Their Applications to Queues[END_REF] and Proposition 3.1 the strategy is now clear: choose any linear topology τ on D([0, 1]) which is coarser than M 1 , then

S n (t) -→ f.d.d. A • Z(t), should imply S n -→ D A • Z on the Skorokhod space D([0, 1]
) equipped with the topology τ . Since convergence of càdlàg functions in the M 1 topology is bounded and implies pointwise convergence outside of a countable set, there are plenty of such topologies. For instance any space of the form L p [0, 1], µ , where p ∈ [0, ∞) and µ is an atomless finite measure on [0, 1], is suitable. The point is to choose the finest among linear topologies with required properties, for we want to have the maximal family of continuous functionals on D([0, 1]),

Although we are not able to identify such an "ideal" topology, we believe that this distinguished position belongs to the S topology, introduced in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF]. This is a non-metric sequential topology, with sequentially continuous addition, which is stronger than any of mentioned above L p (µ) spaces and is functional in the sense it has the following classic property (see Theorem 3.5 of [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF]).

Proposition 3.3 Let Q ⊂ [0, 1] be dense, 1 ∈ Q. Suppose that for each finite subset Q 0 = {q 1 < q 2 < . . . < q m } ⊂ Q we have as n → ∞ (X n (q 1 ), X n (q 2 ), . . . , X n (q m )) -→ D (X 0 (q 1 ), X 0 (q 2 ), . . . , X 0 (q m )),
where X 0 is a stochastic process with trajectories in

D[0, 1]). If {X n } is uniformly S-tight, then X n -→ D X 0 ,
on the Skorokhod space D([0, 1]) equipped with the S topology.

For readers familiar with the limit theory for stochastic processes the above property may seem obvious. But it is trivial only for processes with continuous trajectories. It is not trivial even in the case of the Skorokhod J 1 topology, since the point evaluations

π t : D([0, 1]) → R 1 , π t (x) = x(t),
can be J 1 -discontinuous at some x ∈ D([0, 1]) (see [START_REF] Topsøe | A criterion for weak convergence of measures with an application to convergence of measures on D([0, 1])[END_REF] for the result corresponding to Proposition 3.3). In the S topology the point evaluations are nowhere continuous (see [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF], p. 11). Nevertheless Proposition 3.3 holds for the S topology, while it does not hold for the linear metric spaces L p (µ) considered above. It follows that the S topology is suitable for the needs of limit theory for stochastic processes. It admits even such efficient tools like the a.s Skorokhod representation for subsequences [START_REF] Jakubowski | The a.s. Skorohod representation for subsequences in nonmetric spaces[END_REF]. On the other hand, since D([0, 1]) equipped with S is non-metric and sequential, many of apparently standard reasonings require special tools and careful analysis. This will be seen below.

Before we define the S topology we need some notation. Let V([0, 1]) ⊂ D([0, 1]) be the space of (regularized) functions of finite variation on [0, 1], equipped with the norm of total variation v = v (1), where

v (t) = sup |v(0)| + m i=1 |v(t i ) -v(t i-1 )| ,
and the supremum is taken over all finite partitions 0 = t 0 < t 1 < . . . < t m = t. Since V([0, 1]) can be identified with a dual of (C([0, 1]), • ∞ ), we have on it the weak- * topology. We shall write

v n ⇒ v 0 if for every f ∈ C([0, 1]) [0,1] f (t)dv n (t) → [0,1] f (t)dv 0 (t).
Definition 3.4 (S-convergence and the S topology) We shall say that x n S-converges to x 0 (in short x n → S x 0 ) if for every ε > 0 one can find elements v n,ε ∈ V([0, 1]), n = 0, 1, 2, . . . which are ε-uniformly close to x n 's and weakly- * convergent:

x n -v n,ε ∞ ≤ ε, n = 0, 1, 2, . . . , (30)
v n,ε ⇒ v 0,ε , as n → ∞. ( 31
)
The S topology is the sequential topology determined by the S-convergence.

Remark 3.5 This definition was given in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF] and we refer to this paper for detailed derivation of basic properties of S-convergence and construction of the S topology, as well as for instruction how to effectively operate with S. Here we shall stress only that the S topology emerges naturally in the context of the following criteria of compactness, which will be used in the sequel.

Proposition 3.6 (2.7 in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF]) For η > 0, let N η (x) be the number of ηoscillations of the function x ∈ D([0, 1]), i.e. the largest integer N ≥ 1, for which there exist some points

0 ≤ t 1 < t 2 ≤ t 3 < t 4 ≤ . . . ≤ t 2N -1 < t 2N ≤ 1, such that |x(t 2k ) -x(t 2k-1 )| > η for all k = 1, . . . , N. Let K ⊂ D. Assume that sup x∈K x ∞ < +∞, ( 32
) sup x∈K N η (x) < +∞, for each η > 0. ( 33
)
Then from any sequence {x n } ⊂ K one can extract a subsequence {x n k } and find

x 0 ∈ D([0, 1]) such that x n k -→ S x 0 . Conversely, if K ⊂ D([0, 1]
) is relatively compact with respect to -→ S , then it satisfies both (32) and (33). Corollary 3.7 (2.14 in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF])

Let Q ⊂ [0, 1], 1 ∈ Q, be dense. Suppose that {x n } ⊂ D([0, 1]
) is relatively S-compact and as n → ∞

x n (q) → x 0 (q), q ∈ Q.

Then x n → x 0 in S.

Remark 3.8

The S topology is sequential, i.e. it is generated by the convergence -→ S . By the Kantorovich-Kisyński recipe [START_REF] Kisyński | Convergence du type L[END_REF] x n → x 0 in S topology if, and only if, in each subsequence {x n k } one can find a further subsequence x n k l -→ S x 0 . This is the same story as with a.s. convergence and convergence in probability of random variables.

According to our strategy, we are going to prove that Skorokhod's M 1topology is stronger than the S topology or, equivalently, that x n -→ M 1 x 0 implies x n -→ S x 0 . We refer the reader to the original Skorohod's article [START_REF] Skorokhod | Limit theorems for stochastic processes[END_REF] for the definition of the M 1 topology, as well as to Chapter 12 of [START_REF] Whitt | Stochastic-Process Limits. An Introduction to Stochastic-Process Limits and Their Applications to Queues[END_REF] for a comprehensive account of properties of this topology.

The M 1 -convergence can be described using a suitable modulus of continuity. We define for x ∈ D([0, 1]) and δ > 0

w M 1 (x, δ) := sup 0∨(t 2 -δ)≤t 1 <t 2 <t 3 ≤1∧(t 2 +δ) H x(t 1 ), x(t 2 ), x(t 3 ) , (34)
where H(a, b, c) is the distance between b and the interval with endpoints a and c:

H(a, b, c) = (a ∧ c -a ∧ c ∧ b) ∨ (a ∨ c ∨ b -a ∨ c).
Proposition 3.9 (2.4.1 of [START_REF] Skorokhod | Limit theorems for stochastic processes[END_REF]) Let (x n ) n≥1 and x 0 be arbitrary elements in D([0, 1]). Then

x n -→ M 1
x 0 if, and only if, for some dense subset Q ⊂ [0, 1] containing 0 and 1,

x n (t) → x(t), t ∈ Q, ( 35
)
and lim

δ→0 lim sup n→∞ w M 1 (x n , δ) = 0. ( 36
)
In particular, if x n -→ M 1 x 0 , then

x n (t) → x 0 (t)
for t = 1 and at every point of continuity of x 0 .

Proof. If c ≤ a ≤ b ≤ d, then b -a ≤ d -c = d -c + H(c, a, d) + H(c, b, d). If a ≤ c ≤ b ≤ d then b -a = b -c + c -a ≤ d -c + H(c, a, d) = d -c + H(c, a, d) + H(c, b, d). If a ≤ c ≤ d ≤ b then b -a = b -d + d -c + c -a = H(c, b, d) + d -c + H(c, a, b). If a ≤ b ≤ c ≤ d, then b-a ≤ |b-c|+|c-a| = H(c, b, d)+H(c, a, d) ≤ H(c, b, d)+H(c, a, d)+d-c.
The other cases can be reduced to the considered above.

Corollary 3.11 Let x ∈ D([0, 1]). For any 0 ≤ s ≤ u < v ≤ t ≤ 1, |x(u) -x(v)| ≤ |x(s) -x(t)| + H(x(s), x(u), x(t)) + H(x(s), x(v), x(t)). Lemma 3.12 Let x ∈ D([0, 1]). For 0 ≤ s < t ≤ 1, define β = sup s≤u<v<w≤t H(x(u), x(v), x(w)). If η > 2β then N η (x; [s, t]) ≤ |x(t) -x(s)| + β η -β ,
where N η (x; [s, t]) denotes the number of η-oscillations of x in the interval [s, t].

Proof. Let s ≤ t 1 < t 2 ≤ t 3 < t 4 ≤ . . . ≤ t 2N -1 < t 2N ≤ t be such that |x(t 2k ) -x(t 2k-1 )| > η for all k = 1, . . . , N.
Assume first that x(t 2 ) -x(t 1 ) > η. We claim that

x(t 3 ) ≥ x(t 2 ) -β and x(t 4 ) -x(t 3 ) > η.
To see this, suppose that x(t 3 ) < x(t 2 ) -β. Then the distance between x(t 2 ) and the interval with endpoints x(t 1 ) and x(t 3 ) is greater than β, which is a contradiction. Hence x(t 3 ) ≥ x(t 2 ) -β. On the other hand, if we assume that x(t 4 ) -x(t 3 ) < -η, we obtain that

x(t 1 ) = x(t 1 ) -x(t 2 ) + x(t 2 ) -x(t 3 ) + x(t 3 ) < -η + β + x(t 3 ) < x(t 3 ) -β,
which means that the distance between x(t 3 ) and the interval with endpoints x(t 1 ) and x(t 4 ) is greater than β, again a contradiction.

Repeating this argument, we infer that:

x(t 2k ) -x(t 2k-1 ) > η, for all k = 1, . . . , N and x(t 2k+1 ) -x(t 2k ) > -β for all k = 1, . . . , N -1.

Taking the sum of these inequalities, we conclude that:

x(t 2N ) -x(t 1 ) > N η -(N -1)β = N (η -β) + β. ( 37
)
On the other hand, by Corollary 3.11, we have:

|x(t 2N ) -x(t 1 )| ≤ |x(t) -x(s)| + 2β. ( 38
)
Combining ( 37) and (38), we obtain that

N ≤ |x(t) -x(s)| + β η -β ,
which is the desired upper bound.

Assuming that x(t 2 ) -x(t 1 ) < -η we come in a similar way to the inequality

x(t 2N ) -x(t 1 ) < -N η + (N -1)β = -N (η -β) -β or |x(t 2N ) -x(t 1 )| N (η -β) + β.
This again allows us to use Corollary 3.11 and gives the desired bound for N The following result was stated without proof in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF]. A short proof can be given using Skorohod's criterion 2.2.11 (page 267 of [START_REF] Skorokhod | Limit theorems for stochastic processes[END_REF]) for the M 1 -convergence, expressed in terms of the number of upcrossings. This proof has a clear disadvantage: it refers to an equivalent definition of the M 1 -convergence, but the equivalence of both definitions was not proved in Skorokhod's paper. In the present article we give a complete proof. Theorem 3.13 The S topology is weaker than the M 1 topology (and hence, weaker than the J 1 topology). Consequently, a set A ⊂ D([0, 1]) which is relatively M 1 -compact is also relatively S-compact.

Proof. Let x n -→ M 1 x 0 . By Proposition 3.9

x n (t) → x 0 (t), on the dense set of points of continuity of x 0 and for t = 1. Suppose we know that K = {x n } satisfies conditions (32) and (33). Then by Proposition 3.6 {x n } is relatively S-compact and by Corollary 3.7 x n → x 0 in S. Thus it remains to check conditions

K sup = sup n x n ∞ < +∞, (39)
K η = sup n N η (x n ) < ∞, η > 0. ( 40
)
First suppose that x 0 (1-) = x 0 (1). Then D([0, 1]) ∋ x → x ∞ is M 1 - continuous at x 0 . Consequently, x n -→ M 1 x 0 implies x n ∞ → x 0 ∞ and (39) follows. If x 0 (1-) = x 0 (1)
we have to proceed a bit more carefully. Consider (36) and take δ > 0 and n 0 such that w

(x n , δ) ≤ 1, n ≥ n 0 . Find t 0 ∈ (1 -δ, 1) which is a point of continuity of x 0 . Then sup t∈[0,t 0 ] |x n (t)| → sup t∈[0,t 0 ] |x 0 (t)|,
hence sup n sup t∈[0,t 0 ] |x n (t)| < +∞. We also know that x n (t 0 ) → x 0 (t 0 ) and x n (1) → x 0 (1). Choose n ∈ N and u ∈ (t 0 , 1). By the very definition of the modulus H

|x n (u)| ≤ |x n (t 0 )| + |x n (1)| + H x n (t 0 ), x n (u), x n (1) ≤ sup n |x n (t 0 )| + sup n |x n (1)| + 1, n ≥ n 0 .
It follows that also

sup n sup t∈(t 0 ,1] |x n (t)| < +∞,
and so (39) holds.

In order to prove (40) choose η > 0 and 0 < ε < η/2. By Proposition 3.9, there exist some δ > 0 and an integer n 0 ≥ 1 such that w M 1 (x n , δ) < ε, n ≥ n 0 . Next we find a partition 0 = t 0 < t 1 < . . . < t M = 1 consisting of points of continuity of x 0 and such that t j+1 -t j < δ, j = 0, 1, . . . , M -1.

Again by Proposition 3.9, there exists an integer n 1 ≥ n 0 such that for any n ≥ n 1 |x n (t j ) -x(t j )| < ε, j = 0, 1, . . . , M.

Fix an integer n ≥ n 1 . Suppose that N η (x n ) ≥ N , i.e. there exist some points

0 ≤ s 1 < s 2 ≤ s 3 < s 4 ≤ . . . ≤ s 2N -1 < s 2N ≤ 1, (42)
such that

|x n (s 2k ) -x n (s 2k-1 )| > η, for all k = 1, 2, . . . , N. (43)
The proof of (40) will be complete once we estimate the number N by a constant independent of n.

The η-oscillations of x n determined by (42) can be divided into two (disjoint) groups. The first group (Group 1) contains the oscillations for which the corresponding interval [s 2k-1 , s 2k ) contains at least one point t j ′ . Since the number of points t j is M , the number of oscillations in Group 1 is at most M .

(44)

In the second group (Group 2), we have those oscillations for which the corresponding interval [s 2k-1 , s 2k ) contains no point t j , i.e.

t j ≤ s 2k-1 < s 2k ≤ t j+1 for some j = 0, 1, . . . , M -1. ( 45
)
We now use Lemma 3.12 in each of intervals [t j , t j+1 ], j = 0, 1, . . . , m. Note that β n,j := sup

t j ≤u<v<w≤t j+1 H x n (u), x n (v), x n (w) ≤ w M 1 (x n , δ) < ε, hence, N η (x n , [t j , t j+1 ]) ≤ |x n (t j+1 ) -x n (t j )| + β n,j η -β n,j < 2K sup + ε η -ε .
Since there are M intervals of the form [t j , t j+1 ], we conclude that the number of oscillations in Group 2 is at most

M • 2K sup + ε η -ε (46)
Summing ( 44) and ( 46), we obtain that

N ≤ M 1 + 2K sup + ε η -ε = M 2K sup + η η -ε ,
which does not depend on n. Theorem 3.13 follows.

For the sake of completeness, we provide also a typical example of a sequence (x n ) n≥1 in D[0, 1] which is S-convergent, but does not converge in the M 1 topology. Remark 3.17 In linear topological spaces the algebraic sum K 1 + K 2 = {x 1 + x 2 ; x 1 ∈ K 1 , x 2 ∈ K 2 } of compact sets K 1 and K 2 is compact. It follows directly from the continuity of the operation of addition and trivializes the proof of uniform tightness of sum of uniformly tight random elements. In D([0, 1]) equipped with S we are, however, able to prove that the addition is only sequentially continuous, i.e. if x n -→ S x 0 and y n -→ S y 0 , then x n +y n -→ S x 0 +y 0 . In general it does not imply continuity (see [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF], p. 18, for detailed discussion). Sequential continuity gives a weaker property: the sum K 1 + K 2 of relatively S-compact K 1 and K 2 is relatively S-compact. For the uniform tightness purposes we also need that the S-closure of K 1 + K 2 is again relatively S-compact. This is guaranteed by the lower-semicontinuity in S of • ∞ and N η (see [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF], Corollary 2.10).

The main result

Theorem 3.18 Let {Y j } be an i.i.d. sequence satisfying the usual conditions and j |c j | < +∞. Let S n (t) be defined by [START_REF] Esary | Association of random variables with applications[END_REF] and T n (t) by ( 16). Then

T n (t) -→ f.d.d. A |•| • Z(t), where A |•| = j |c j |, implies S n -→ D A • Z, where A = j c j ,
on the Skorokhod space D([0, 1]) equipped with the S topology.

Proof. By Corollary 2.2

T + n (t) = 1 a n [nt] i=1 X + i -→ f.d.d. A + • Z(t), T - n (t) = 1 a n [nt] i=1 X - i -→ f.d.d. A -• Z(t),
where

A + = i∈Z c + i and A -= i∈Z c - i . It follows from Proposition 3.1 that T + n -→ D A + • Z on D([0, 1]
) equipped with the M 1 topology. A similar result holds for T - n . Since the law of every càdlàg process is M 1 -tight, Le Cam's theorem [START_REF] Cam | Convergence in distribution of stochastic processes[END_REF] (see also Theorem 8 in Appendix III of [START_REF] Billingsley | Convergence of Probability Measures[END_REF]) guarantees that both sequences {T + n } and {T - n } are uniformly M 1 -tight. By Theorem 3.13 we obtain the uniform S-tightness of both {T + n } and {T - n }. Again by Corollary 2.2

S n (t) = T + n (t) -T - n (t) -→ f.d.d. A • Z(t).
Now a direct application of Proposition 3.16 completes the proof of the theorem.

Discussion of sufficient conditions

Conditions ( 14) do not look tractable. In what follows we shall provide three types of checkable sufficient conditions. In both cases the following slight simplification (47) of ( 14) will be useful. As in proof of Lemma 2.3, we can find a sequence j n → ∞,

j n = o(n), such that 0 j=-jn+1 d n,j α a α n h a n d n,j → 0, as n → ∞. n+jn-1 j=n+1 d n,j α a α n h a n d n,j → 0, as n → ∞.
Hence it is enough to check

-jn j=-∞ d n,j α a α n h a n d n,j → 0, as n → ∞. +∞ j=n+jn d n,j α a α n h a n d n,j → 0, as n → ∞. (47)
The advantage of this form of the conditions consists in the fact that sup j≤-jn

d n,j → 0, as n → ∞, sup j≥n+jn d n,j → 0, as n → ∞. ( 48
)
We will write -→ D(S) when convergence in distribution with respect to the S topology takes place.

< β < α, β ≤ 1 such that j∈Z |c j | β < +∞, ( 49
) then S n (t) -→ D(S) A • Z(t).
Proof. We have to check (47). By simple manipulations and taking into account that due to (6

) K = sup n na -α n h(a n ) < +∞ we obtain -jn j=-∞ d n,j α a α n h a n d n,j = 1 n -jn j=-∞ n-j k=1-j c k β nh(a n ) a α n d n,j α-β 1 h(a n ) h a n d n,j ≤ K 1 n -jn j=-∞ n-j k=1-j |c k | β Ψ α-β a n , a n d n,j ,
where

Ψ α-β (x, y) = x y α-β h(y) h(x) . Let h(x) = c(x) exp x a ǫ(u) u du ,
where lim x→∞ c(x) = c ∈ (0, ∞) and lim x→∞ ǫ(x) = 0, be the Karamata representation of the slowly varying function h(x) (see e.g. Theorem 1.3.1 in [START_REF] Bingham | Regular Variation Encyclopedia Math[END_REF]). Take 0 < γ < min{α -β, c} and let L > a be such that for x > L ǫ(x) ≤ γ and c -γ < c(x) < c + γ.

Then we have for

x ≥ y ≥ L h(y) h(x) = c(y) c(x) exp x y ǫ(u) u du ≤ c + γ c -γ exp γ log x y = c + γ c -γ x y γ ,
and so

Ψ α-β (x, y) ≤ K y x α-β-γ , x ≥ y ≥ L.
It follows from that fact and (48) that

sup j≤-jn Ψ α-β a n , a n d n,j → 0, as n → ∞.
Hence it is sufficient to show that

sup n 1 n -jn j=-∞ n-j k=1-j |c k | β < +∞.
In fact, more is true.

Lemma 4.2 If ∞ j=0 |b j | < +∞, then for each t > 0 1 n ∞ j=0 n+j k=1+j b k → 0, as n → ∞.
Proof of Lemma 4.2 We have

1 n ∞ j=0 n+j k=1+j b k ≤ 1 n ∞ j=0 n+j k=1+j |b k | = 1 n ∞ k=1 (k ∧ n)|b k | = 1 n n k=1 k|b k | + ∞ k=n+1 |b k | .
The first sum in the last line converges to 0 by Kronecker's lemma. The second is the rest of a convergent series.

Returning to the proof of Corollary 4.1, let us notice that convergence

+∞ j=n+jn d n,j α a α n h a n d n,j → 0, as n → ∞,
can be checked the same way.

Corollary 4.3 Under the usual conditions, if α ∈ (1, 2) and j∈Z |c j | < +∞, then S n (t) -→ D(S) A • Z(t).
Remark 4.4 Corollaries 4.1 and 4.3 were proved independently by Astrauskas [START_REF] Astrauskas | Limit theorems for sums of linearly generated random variables[END_REF] and Davis and Resnick [START_REF] Davis | Limit theory for moving averages of random variables with regularly varying tail probabilities[END_REF]. Our approach follows direct manipulations of Astrauskas, while Davis and Resnick involved point process techniques.

Remark 4.5 For α ≤ 1 assumption (49) is unsatisfactory, for it excludes the case of strictly α-stable random variables {Y j } with j |c j | α < +∞, but j |c j | β = +∞ for every β < α. With our criterion given in Theorem 2.1 we can easily prove the needed result.

Corollary 4.6 Suppose that α ≤ 1, j∈Z |c j | α < +∞, the usual conditions hold and h is such that

h(λx)/h(x) ≤ M, λ ≥ 1, x ≥ x 0 , (50)
for some constants M , x 0 . If the linear process {X i } is well-defined, then

S n (t) -→ D(S) A • Z(t).
Proof of Corollary 4.6 First notice that j |c j | < +∞ so that A is defined.

Proceeding like in the proof of Corollary 4.1 we obtain

-jn j=-∞ d n,j α a α n h a n d n,j = 1 n -jn j=-∞ n-j k=1-j c k α nh(a n ) a α n 1 h(a n ) h a n d n,j ≤ K • M 1 n -jn j=-∞ n-j k=1-j |c k | α → 0,
where the convergence to 0 holds by Lemma 4.2.

Remark 4.7 As mentioned before, the above corollary covers the important case when h(x) → C > 0, as x → ∞, i.e. when the law of Y i is in the domain of strict (or normal) attraction. Many other examples can be produced using Karamata's representation of slowly varying functions. Assumption (50) is much in the spirit of Lemma A.4 in [START_REF] Mikosch | The Supremum of a Negative Drift Random Walk with Dependent Heavy-Tailed Steps[END_REF]. Our final result goes in different direction.

Remark 4.8 Notice that if α < 1, then j |c j | α h(|c j | -1 ) < +∞, with h slowly varying, automatically implies j |c j | < +∞.

Corollary 4.9 Under the usual conditions, if α < 1, then

S n (t) -→ D(S) A • Z(t), if j∈Z |c j | α < +∞,
and the coefficients c j are regular in a very weak sense: there exists a constant 0 < γ < α such that

max j+1≤k≤j+n |c k | (1-α)(α-γ) (1-α+γ) j+n k=j+1 |c k | α ≤ K + < +∞, j ≥ 0. ( 51
) max j-n≤k≤j-1 |c k | (1-α)(α-γ) (1-α+γ) j-1 k=j-n |c k | α ≤ K -< +∞, j ≤ 0. ( 52
)
(with the convention that 0/0 ≡ 1.)

Remark 4.10 Notice that we always assume that the linear process is well defined. This may require more than demanded in Corollary 4.9.

Proof of Corollary 4.9 As before, we have to check (47).

-jn

j=-∞ d n,j α a α n h a n d n,j = 1 n -jn j=-∞ n-j k=1-j c k α-γ nh(a n ) a α n d n,j γ 1 h(a n ) h a n d n,j ≤ K 1 n -jn j=-∞ n-j k=1-j c k α-γ Ψ γ a n , a n d n,j ,
where Ψ γ (x, y) was defined in the proof of Corollary 4.1 and sup j≤-jn

Ψ γ a n , a n d n,j → 0, as n → ∞.
Thus it is enough to prove

sup n 1 n -jn j=-∞ n-j k=1-j c k α-γ < +∞.
We have

n-j k=1-j c k ≤ n-j k=1-j |c k | ≤ n-j k=1-j |c k | α • max 1-j≤k≤n-j |c k | 1-α , (53) hence 1 n
-jn j=-∞ n-j k=1-j c k α-γ = 1 n -jn j=-∞ n-j k=1-j |c k | α n-j k=1-j c k α-γ n-j k=1-j |c k | α ≤ 1 n -jn j=-∞ n-j k=1-j |c k | α max 1-j≤k≤n-j |c k | (1-α)(α-γ) n-j k=1-j |c k | α 1-α+γ ≤ K + 1-α+γ 1 n -jn j=-∞ n-j k=1-j |c k | α → 0.
This is again more than needed. The proof of

+∞ j=n+jn d n,j α a α n h a n d n,j → 0, as n → ∞.
goes the same way.

Example 4.11 If α < 1,

|c j | = 1 |j| 1/α log (1+ε)/α |j| , |j| ≥ 3,
and {X i } is well-defined, then under the usual conditions

S n (t) -→ D(S) A • Z(t).
Remark 4.12 In our considerations we search for conditions giving functional convergence of {S n (t)} with the same normalization as {Z n (t)} (by {a n }). It is possible to provide examples of linear processes, which are convergent in the sense of finite dimensional distribution with different normalization. Moreover, it is likely that also in the heavy-tailed case one can obtain a complete description of the convergence of linear processes, as it is done by Peligrad and Sang [START_REF] Peligrad | Central limit theorem for linear processes with infinite variance[END_REF] in the case of innovations belonging to the domain of attraction of a normal distribution. We conjecture that whenever the limit is a stable Lévy motion our functional approach can be adapted to the more general setting.

5 Some complements

S-continuous functionals

A phenomenon of self-cancelling oscillations, typical for the S topology, was described in Example 3.14. This example shows that supremum cannot be continuous in the S topology. In fact, supremum is lower semi-continuous with respect to S, as many other popular functionals -see [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF], Corollary 2.10. On the other hand addition is sequentially continuous and this property was crucial in consideration given in Section 3.4. Here is another positive example of an S-continuous functional.

Let µ be an atomless measure on [0, 1] and let h : R 1 → R 1 be a continuous function. Consider a smoothing operation s µ,h on D([0, 1]) given by the formula

s µ,h (x)(t) = t 0 h(x(s)) dµ(s).
Then s µ,h (x)(•) is a continuous function on [0, 1] and a slight modification of the proof of Proposition 2.15 in [START_REF] Jakubowski | A non-Skorohod topology on the Skorohod space[END_REF] shows that the mapping

D([0, 1]), S ∋ x → s µ,h (x) ∈ C([0, 1]), • ∞ is continuous.
In particular, if we set µ = ℓ (the Lebesgue measure), h(0) = 0, h(x) ≥ 0, and suppose that x n -→ S 0, then 1 0 h(x n (s)) ds → 0.

In the case of linear processes such functionals lead to the following result. Proof of Corollary 5.1 The expression to be analyzed has the form

1 0 H β S n (t) -A • Z n (t) dt,
where H β (x) = |x| β and by ( 26)

S n (t) -A • Z n (t) -→ f.d.d.

0.

We have checked in the course of the proof of Theorem 3.18, that {S n } is uniformly S-tight. By (3) {A • Z n } is uniformly J 1 -tight, hence also S-tight.

Similarly as in the proof of Proposition 3.16 we deduce that {S n -A • Z n } is uniformly S-tight. Now an application of Proposition 3.3 gives

S n -A • Z n -→ D 0,
on the Skorokhod space D([0, 1]) equipped with the S topology.

An example related to convergence in the M 1 topology

In Introduction we provided an example of a linear process (c 0 = 1, c 1 = -1) for which no Skorokhod's convergence is possible. In this example A = 0 and the limit is degenerate, what might suggest that another, more appropriate norming is applicable, under which the phenomenon disappears. Here we give an example with a non-degenerate limit showing that in the general case M 1 -convergence need not hold.

Example 5.2 Let c 0 = ζ > -c 1 = ξ > 0.
Then X j = ζY j -ξY j-1 and defining Z n (t) by ( 3) we obtain for t ∈ [k/n, (k + 1)/n)

S n (t) = 1 a n k j=1 X j = 1 a n ζY k -ξY 0 + ζ -ξ)Z n ((k -1)/n).
Clearly, the f.d.d. limit { ζ -ξ)Z(t)} is non-degenerate. We will show that the sequence {S n (t)} is not uniformly M 1 -tight and so cannot converge to { ζ -ξ)Z(t)} in the M 1 topology. For the sake of simplicity let us assume that Y j 's are non-negative and

P Y 1 > x = x -α , x ≥ 1,
with α < 1. Then we can choose a n = n 1/α . Consider sets

G n = n-1 j=0 Y j > ε n a n , Y j+1 > ε n a n .
where ε n = n -1/(3α) . Then

P G n ≤ (n + 1)P Y i > ε n a n 2 = (n + 1)ε -2α n n 1/α -2α -→ 0.
Notice that on G c n there are no two consecutive values of Y j exceeding ε n a n .

Let us define Y n,j = Y j 1I{Y j > ε n a n } and set for t ∈ [k/n, (k + 1)/n)

S n (t) = 1 a n ζY n,k -ξY n,0 + ζ -ξ a n k-1 j=1
Y n,j .

We have by ( 61)

E sup t∈[0,1] S n (t) -S n (t) ≤ ζ a n n j=0 E Y j 1I{Y j ≤ ε n a n } ≤ C 1 ζ (n + 1)(ε n a n ) 1-α a n → 0.
It follows that {S n (t)} are uniformly M 1 -tight if, and only if, { S n (t)} are. Let w M 1 (x, δ) be given by (34). Since P G c n → 1 we have for any δ > 0 and η > 0 lim sup

n P w M 1 ( S n (•), δ) > η = lim sup n P {w M 1 ( S n (•), δ) > η} ∩ G c n .
And on G c n , by the property (54) and if 2/n < δ we have

ω( S n (•), δ) ≥ 1 a n ζ -ξ max j Y n,j . If η/(ζ -ξ) > ε n , then P (1/a n ) max j Y n,j > η/ ζ -ξ = P (1/a n ) max j Y j > η/ ζ -ξ -→ 1 -exp -(ζ -ξ)/η α = θ > 0.
Hence for each δ > 0 lim inf

n P w M 1 ( S n (•), δ) > η ≥ θ > 0,
and the sequence { S n (t)} cannot be uniformly M 1 -tight.

Linear space of convergent linear processes

We can explore the machinery of Section 4 to obtain a natural Proposition 5.3 We work under the assumptions of Theorem 2.1. Denote by C Y the set of sequences {c i } i∈Z such that if

X i = j∈Z c j Y i-j , i ∈ Z, then S n (t) = 1 a n [nt] i=1 X i -→ f.d.d. A • Z(t), with A = i∈Z c i . Then C Y is a linear subspace of R Z .
Proof of Proposition 5.

P n-j k=1-j (c ′ k + c ′′ k ) |Y j | > a n → 0, as n → ∞. ∞ j=n+1 P n-j k=1-j (c ′ k + c ′′ k ) |Y j | > a n → 0, as n → ∞. ( 55
) But 0 j=-∞ P n-j k=1-j (c ′ k + c ′′ k ) |Y j | > a n ≤ 0 j=-∞ P n-j k=1-j c ′ k |Y j | + n-j k=1-j c ′′ k |Y j | > a n ≤ 0 j=-∞ P n-j k=1-j c ′ k |Y j | > a n /2 + 0 j=-∞ P n-j k=1-j c ′′ k |Y j | > a n /2 .
Now both terms tend to 0 by Remark 2.7. Identical reasoning can be used in the proof of the "dual" condition in (55).

Dependent innovations

In the main results of the paper we studied only independent innovations {Y j }. It is however clear that the functional S-convergence can be obtained under much weaker assumptions. In order to apply crucial Proposition 3.16 we need only that

S n (t) -→ f.d.d. A • Z(t),
and that

T + n -→ D A + • Z, and T - n -→ D A -• Z,
on the Skorokhod space D([0, 1]) equipped with the M 1 topology. For the latter relations Theorem 1 of [START_REF] Louhichi | Functional convergence to stable Lévy motions for iterated random Lipschitz mappings[END_REF] seems to be an ideal tool for associated sequences (see our Proposition 3.1). A variety of potential other possible examples is given in [START_REF] Tyran-Kamińska | Functional limit theorems for linear processes in the domain of attraction of stable laws[END_REF].

Appendix

We provide two results of a technical character. The first one is well-known ( [START_REF] Astrauskas | Limit theorems for sums of linearly generated random variables[END_REF]) and is stated here for completeness. Proposition 6.2 might be of independent interest.

Proposition 6.1 Let {Y j } be an i.i.d.sequence satisfying ( 4), ( 7) and ( 8) and let {c j } be a sequence of numbers. Then the series j∈Z c j Y j is well defined if, and only if,

j∈Z |c j | α h(|c j | -1 ) < +∞. ( 56
)
Proposition 6.2 Let {Y j } be an i.i.d.sequence satisfying (4), [START_REF] Bulinski | Limit Theorems for Associated Random Fields and Related Systems[END_REF] and [START_REF] Davis | Limit theory for moving averages of random variables with regularly varying tail probabilities[END_REF].

Consider an array {c n,j ; n ∈ N, j ∈ Z} of numbers such that for each n

∈ N j∈Z |c n,j | α h(|c n,j | -1 ) < +∞. ( 57
) Set V n = j∈Z c n,j Y j , n ∈ N. Then V n -→ P 0 (58)
if, and only if,

j∈Z |c n,j | α h(|c n,j | -1 ) → 0, as n → ∞ . (59)
In the proofs we shall need some estimates which seem to be a part of the probabilistic folklore.

E Y 2 I |Y | ≤ x ≤ C 2 x 2-α h(x), x > 0. ( 60
)
(ii) If α ∈ (0, 1), then there exists a constant C 1 , depending on α and the law of Y such that

E |Y |I |Y | ≤ x ≤ C 1 x 1-α h(x), x > 0. ( 61
) (iii) If α ∈ (1, 2)
, then there is x 0 > 0, depending on the law of Y , such that

E |Y |I |Y | > x ≤ E |Y | I x ≤ x 0 + 2α α -1 x 1-α h(x), x > 0. ( 62
)
Proof. Take β > α. Applying the direct half of Karamata's Theorem (Th. 1.5.11 [START_REF] Bingham | Regular Variation Encyclopedia Math[END_REF]) we obtain

E |Y | β I |Y | ≤ x = β x 0 t β-1 P |Y | > t dt-x β P |Y | > t ∼ α β -α x β-α h(x).
Hence there exists x 0 such that

E |Y | β I |Y | ≤ x ≤ 2α β -α x β-α h(x), x > x 0 . If 0 < x ≤ x 0 , then E |Y | β I |Y | ≤ x ≤ x β = x β x -α h(x) P |Y | > x ≤ 1 P |Y | > x 0
x β-α h(x).

Setting C β = max{1/P |Y | > x 0 , 2α/(β -α)} one obtains both (60) and (61).

To get (62) we proceed similarly. First, by Karamata's Theorem We have proved the sufficiency part of Proposition 6.2.

To prove the "only if" part, we show first that V n -→ P 0 implies uniform infinitesimality of the coefficients, that is sup j∈Z |c n,j | → 0, as n → ∞.

(68)

Let { Ȳj } be an independent copy of {Y j }. If Vn = j∈Z c n,j Ȳj , then also V n -Vn -→ P 0 and these are series of symmetric random variables. For each n select some arbitrary j n ∈ Z and consider decomposition into independent symmetric random variables

V n -Vn = c n,jn (Y jn -Ȳjn ) + j∈Z,j =jn c n,j (Y j -Ȳj ) = W n + W n .

Since {V n -Vn } n∈N is uniformly tight, so is {W n } n∈N (it follows from the Lévy-Ottaviani inequality, see e.g. Proposition 1.1.1 in [START_REF] Kwapień | Random Series and Stochastic Integrals: Single and Multiple[END_REF]). Since the law of Y j -Ȳj is non-degenerate we obtain This completes the proof of Proposition 6.2.

Lemma 3 . 10

 310 For any a, b, c, d ∈ R 1 |a -b| ≤ |c -d| + H(c, a, d) + H(c, b, d).

Corollary 4 . 1

 41 Under the assumptions of Theorem 2.1, if there exists 0

Corollary 5 . 1

 51 Under the conditions of Corollaries 4.1, 4.3, 4.6 or 4.9 we have for any β >

Lemma 6 . 3

 63 Assume thatP |Y | > x = x -α h(x),where h(x) is slowly varying at x = ∞.(i) If α ∈ (0, 2), then there exists a constant C 2 , depending on α and the law of Y such that

EP 2 j∈Z |c j | 2 ( 1 /C 1 j∈Z

 2211 |Y |I |Y | > x = ∞ x |Y | > t dt + xP |Y | > x ∼ α α -1 x 1-α h(x),Hence for some x 0 we haveE|Y |I |Y | > x ≤ 2α α -1 x 1-α h(x), x > x 0 .Since α > 1, we have E |Y | < +∞ and (62) follows.Proof of Proposition 6.1 We begin with specifying the conditions of the Kolmogorov Three Series Theorem in terms of our linear sequences. We havej∈Z P |c j Y j | > 1 = j∈Z ( 1 |c j | ) -α h(|c j | -1 ) = j∈Z |c j | α h(|c j | -1 ). (63)Applying (60) we obtain j∈ZVar (c j Y j )I |c j Y j | ≤ 1 ≤ j∈Z E c j Y j 2 I |c j Y j | ≤ 1 = j∈Z |c j | 2 E Y 2 j I(|Y j | ≤ 1/|c j |) ≤ C |c j |) 2-α h(|c j | -1 ) = C 2 j∈Z |c j | α h(|c j | -1 ).(64)Similarly, if α ∈ (0, 1), then by (61)j∈Z E c j Y j I |c j Y j | ≤ 1 ≤ j∈Z |c j |E |Y j |I |Y j | ≤ 1/|c j | ≤ C 1 j∈Z |c j |(1/|c j |) 1-α h(|c j | -1 ) = |c j | α h(|c j | -1 ).(65)If α = 1, then by the symmetry we have E Y j I |Y j | ≤ a = 0, a > 0, and the series of truncated expectations trivially vanishesj∈Z E c j Y j I |c j Y j | ≤ 1 = 0. (66)For α ∈ (1, 2) we have E X j = 0 and by (62) j∈Z |E c j Y j I |c j Y j | ≤ 1 | = j∈Z |E c j Y j I |c j Y j | > 1 | ≤ j∈Z |c j |E |Y j |I |Y j | > 1/|c j | ≤ E |Y | max j∈Z |c j |#{j ; |c j | ≥ 1/x 0 } + 2α α -1 j∈Z |c j |(1/|c j |) 1-α h(|c j | -1 )(67)By (63) -(67) we obtain that j∈Z |c j | α h(|c j | -1 ) < +∞ if, and only if, all the assumptions of the Three Series Theorem are satisfied. Hence j∈Z c j Y j is a.s. convergent if, and only if, (56) holds.Proof of Proposition 6.2 By Proposition 6.1 all random variables V n = j∈Z c n,j Y j are well-defined. Let us consider a decomposition of each V n into a sum of another three (convergent!) series:V n = j∈Z c n,j Y j I(|c n,j Y j | ≤ 1) -E c n,j Y j I(|c n,j Y j | ≤ 1) + j∈Z E c n,j Y j I(|c n,j Y j | ≤ 1) + j∈Z c n,j Y j I(|c n,j Y j | > 1) =V n,1 + V n,2 + V n,3 .By (64) we haveVar V n,1 ≤ C 2 j∈Z |c n,j | α h(|c n,j | -1 ) → 0, as n → ∞, if(59) holds. Similarly V n,2 → 0 by (65) -(67). Finally, we have P V n,3 = 0) ≤ P j∈Z {|c n,j Y j | > 1} ≤ j∈Z P |c n,j Y j | > 1 = j∈Z |c n,j | α h(|c n,j | -1 ) → 0 as n → ∞.

  sup n |c n,jn | < +∞.If along some subsequence n ′ we would have c n ′ ,j n ′ → c = 0, then for some θ ∈ R1 limn ′ →∞ E e iθW n ′ = |E e iθcY | 2 < 1.It follows that alsolim n ′ →∞ E e iθ(V n ′ -Vn ′ ) = lim n ′ →∞ E e iθW n ′ E e iθ W n ′ < 1.This is in contradiction with V n -Vn -→ P 0. Hence c = 0, c n,jn → 0 and since j n was chosen arbitrary, (68) follows. Now let us choose k n such that both|j|>kn c n,j Y j -→ P 0, as n → ∞,and |j|>kn P |c n,j Y j | > 1 → 0, as n → ∞.Then {X n,j = c n,j Y j ; |j| ≤ k n , n ∈ N} is an infinitesimal array of row-wise independent random variables, with row sums convergent in probability to zero. Applying the general central limit theorem (see e.g. Theorem 5.15 in[START_REF] Kallenberg | Foundations of Modern Probability[END_REF]) we obtain |j|≤kn P |X n,j | > 1 = |j|≤kn P |c n,j Y j | > 1 = |j|≤kn |c n,j | α h(|c n,j | -1 ) → 0.

3

  Closeness of C Y under multiplication by a number is obvious. So let us assume that {c ′ i } and {c ′′ i } are elements of C Y . By Theorem 2.1 we have to prove that

	0
	j=-∞

Acknowledgement. The authors would like to thank the anonymous referee for careful reading of the manuscript and comments which improved the paper in various aspects.

* Research of R. M. Balan was supported by a grant from NSERC of Canada

Example 3.14 Let x = 0 and

Then x n -→ S x. To see this, we take v n,ε = x n . Then v n,ε ⇒ v ε = 0 since for any f ∈ C[0, 1],

The fact that (x n ) n≥1 cannot converge in M 1 follows by Proposition 3.9 since if

Convergence in distribution in the S topology

Now we are ready to specify results on functional convergence of stochastic processes in the S topology, which are suitable for needs of linear processes. They follow directly from Proposition 3.6 and Proposition 3.3. ) such that as n → ∞

X n (q 1 ) + Y n (q 1 ), X n (q 2 ) + Y n (q 2 ), . . . , X n (q k ) + Y n (q k ) -→ D X 0 (q 1 ) + Y 0 (q 1 ), X 0 (q 2 ) + Y 0 (q 2 ) . . . , X 0 (q k ) + Y 0 (q k ) ,


Sunil Arya
email: arya@cse.ust.hk

Guilherme D Da Fonseca

David M Mount
email: mount@cs.umd.edu

Approximate Convex Intersection Detection with Applications to Width and Minkowski Sums

Approximation problems involving a single convex body in R d have received a great deal of attention in the computational geometry community. In contrast, works involving multiple convex bodies are generally limited to dimensions d ≤ 3 and/or do not consider approximation. In this paper, we consider approximations to two natural problems involving multiple convex bodies: detecting whether two polytopes intersect and computing their Minkowski sum. Given an approximation parameter ε > 0, we show how to independently preprocess two polytopes A, B ⊂ R d into data structures of size O(1/ε (d-1)/2 ) such that we can answer in polylogarithmic time whether A and B intersect approximately. More generally, we can answer this for the images of A and B under affine transformations. Next, we show how to ε-approximate the Minkowski sum of two given polytopes defined as the intersection of n halfspaces in O(n log(1/ε) + 1/ε (d-1)/2+α ) time, for any constant α > 0. Finally, we present a surprising impact of these results to a well studied problem that considers a single convex body. We show how to ε-approximate the width of a set of n points in O(n log(1/ε) + 1/ε (d-1)/2+α ) time, for any constant α > 0, a major improvement over the previous bound of roughly O(n + 1/ε d-1 ) time.

Introduction

Approximation problems involving a single convex body in d-dimensional space have received a great deal of attention in the computational geometry community [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF][START_REF] Arya | On the combinatorial complexity of approximating polytopes[END_REF][START_REF] Arya | Optimal approximate polytope membership[END_REF][START_REF] Arya | Approximate polytope membership queries[END_REF][START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF][START_REF] Chan | Applications of Chebyshev polynomials to low-dimensional computational geometry[END_REF][START_REF] Yu | Practical methods for shape fitting and kinetic data structures using coresets[END_REF]. Recent results include near-optimal algorithms for approximating the convex hull of a set of points [START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF][START_REF] Chan | Applications of Chebyshev polynomials to low-dimensional computational geometry[END_REF], as well as an optimal data structure for answering approximate polytope membership queries [START_REF] Arya | Optimal approximate polytope membership[END_REF]. In contrast, works involving multiple convex bodies are generally limited to dimensions d ≤ 3 and/or do not consider approximation [START_REF] Agarwal | Penetration depth of two convex polytopes in 3D[END_REF][START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF][START_REF] Fogel | On the exact maximum complexity of Minkowski sums of polytopes[END_REF][START_REF] Guo | Optimal accurate Minkowski sum approximation of polyhedral models[END_REF][START_REF] Varadhan | Accurate Minkowski sum approximation of polyhedral models[END_REF]. In this paper we present new approximation algorithms to natural problems that either involve multiple convex polytopes or result from such an analysis:

• Determining whether two convex polytopes A and B intersect • Computing the Minkowski sum, A ⊕ B, of two convex polytopes

• Computing the width of a convex polytope A (which results from an analysis of the Minkowski sum A ⊕ (-A))

Throughout we assume that the input polytopes reside in R d and are full-dimensional, where the dimension d is a fixed constant. Polytopes may be represented either as the convex hull of n points (point representation) or as the intersection of n halfspaces (halfspace representation). In either case, n denotes the size of the polytope.

Convex Intersection

Detecting whether two geometric objects intersect and computing the region of intersection are fundamental problems in computational geometry. Geometric intersection problems arise naturally in a number of applications. Examples include geometric packing and covering, wire and component layout in VLSI, map overlay in geographic information systems, motion planning, and collision detection. Several surveys present the topics of collision detection and geometric intersection [START_REF] Jiménez | 3D collision detection: A survey[END_REF][START_REF] Lin | Collision detection between geometric models: A survey[END_REF][START_REF] Mount | Geometric intersection[END_REF].

The special case of detecting the intersection of convex objects has received a lot of attention in computational geometry. The static version of the problem has been considered in R 2 [START_REF] O'rourke | Computational geometry in C[END_REF][START_REF] Shamos | Geometric complexity[END_REF] and R 3 [START_REF] Chazelle | An optimal algorithm for intersecting three-dimensional convex polyhedra[END_REF][START_REF] Muller | Finding the intersection of two convex polyhedra[END_REF]. The data structure version where each convex object is preprocessed independently has been considered in R 2 [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF][START_REF] Chazelle | Detection is easier than computation[END_REF][START_REF] Chazelle | Intersection of convex objects in two and three dimensions[END_REF][START_REF] Dobkin | Fast detection of polyhedral intersection[END_REF] and R 3 [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF][START_REF] Chazelle | Intersection of convex objects in two and three dimensions[END_REF][START_REF] Dobkin | Fast detection of polyhedral intersection[END_REF][START_REF] Dobkin | Determining the separation of preprocessed polyhedra-A unified approach[END_REF].

Recently, Barba and Langerman [START_REF] Barba | Optimal detection of intersections between convex polyhedra[END_REF] considered the problem in higher dimension. They showed how to preprocess convex polytopes in R d so that given two such polytopes that have been subject to affine transformations, it can be determined whether they intersect each other in logarithmic time. However, the preprocessing time and storage grow as the combinatorial complexity of the polytope raised to the power d/2 . Since the combinatorial complexity of a polytope with n vertices can be as high as Θ(n d/2 ), the storage upper bound is roughly O(n d 2 /4 ). This high complexity motivates the study of approximations to the problem.

We define approximation in a manner that is sensitive to direction. Consider any convex body K in R d and any ε > 0. Given a nonzero vector v ∈ R d , define Π v (K) to be the minimum slab defined by two hyperplanes that enclose K and are orthogonal to v. Define the directional width of K with respect to v, width v (K), to be the perpendicular distance between these hyperplanes. Let Π v,ε (K) be the central expansion of Π v (K) by a factor of 1 + ε, and define K ε to be the intersection of these expanded slabs over all unit vectors v. It can be shown that for any v, width v (K ε ) = (1 + ε) width v (K). An ε-approximation of K is any set K (which need not be convex) such that K ⊆ K ⊆ K ε . This defines an outer approximation. It is also possible to define an analogous notion of inner approximation in which each directional width is no smaller than 1 -ε times the true width. Our results can be extended to either type of approximation.

A related notion studied extensive in the literature is that of ε-kernels. Given a discrete point set S in R d , an ε-kernel of S is any subset Q ⊆ S such that conv(Q) is an inner ε-approximation of conv(S) [START_REF] Agarwal | Approximating extent measures of points[END_REF]. It is well known that O(1/ε (d-1)/2 ) points are sufficient and sometimes necessary in an ε-kernel. Kernels efficiently approximate the convex hull and as such have been used to obtain fast approximation algorithms to several problems such as diameter, minimum width, convex hull volume, minimum enclosing cylinder, minimum enclosing annulus, and minimum-width cylindrical shell [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Agarwal | Geometric approximation via coresets[END_REF].

In the ε-approximate version of convex intersection, we are given two convex bodies A and B and a parameter ε > 0.

If A ∩ B = ∅, then the answer is "yes." If A ε ∩ B ε = ∅, then the answer is "no."
Otherwise, either answer is acceptable. The ε-approximate polytope intersection problem is defined as follows. A collection of two or more convex polytopes in R d are individually preprocessed (with knowledge of ε). Given any two preprocessed polytopes, A and B, the query determines whether A and B intersect approximately. In general, the query algorithm can be applied to any affine transformation of the preprocessed polytopes.

Theorem 1. Given a parameter ε > 0 and two polytopes A, B ⊂ R d each of size n (given either using a point or halfspace representation), we can independently preprocess each polytope into a data structure in order to answer ε-approximate polytope intersection queries with query time O(polylog 1 ε ), storage O(1/ε (d-1)/2 ), and preprocessing time O(n

log 1 ε + 1/ε (d-1)/2+α
), where α is an arbitrarily small positive constant.

The space is nearly optimal in the worst case because there is a lower bound of Ω(1/ε (d-1)/2 ) on the worst-case bit complexity of representing an ε-approximation of a polytope [START_REF] Arya | Optimal approximate polytope membership[END_REF].

⊕ = A B A ⊕ B ⊕ = A -A A ⊕ -A w w (a) (b)
Figure 1: Minkowski sum and its relationship to width.

Minkowski Sum

Given two convex bodies A, B ⊂ R d , the Minkowski sum A ⊕ B is defined as {p + q : p ∈ A, q ∈ B} (see Figure 1(a)). Minkowski sums have found numerous applications in motion planning [START_REF] Aronov | On translational motion planning of a convex polyhedron in 3-space[END_REF][START_REF] Halperin | Algorithmic motion planning[END_REF], computer-aided design [START_REF] Varadhan | Accurate Minkowski sum approximation of polyhedral models[END_REF], computational biology [START_REF] Pachter | Algebraic statistics for computational biology[END_REF], satellite layout [START_REF] Boissonnat | Minkowski operations for satellite antenna layout[END_REF], and image processing [START_REF] Kaul | Solid-interpolating deformations: construction and animation of pips[END_REF]. Minkowski sums have also been well studied in the context of discrete and computational geometry [START_REF] Agarwal | Polygon decomposition for efficient construction of Minkowski sums[END_REF][START_REF] Agarwal | Union of random Minkowski sums and network vulnerability analysis[END_REF][START_REF] Fogel | On the exact maximum complexity of Minkowski sums of polytopes[END_REF][START_REF] Har-Peled | The complexity of a single face of a Minkowski sum[END_REF][START_REF] Tiwary | On the hardness of computing intersection, union and Minkowski sum of polytopes[END_REF].

It is well known that in dimension d ≥ 3, the number of vertices in the Minkowski sum of two polytopes can grow as rapidly as the product of the number of vertices in the two polytopes [START_REF] Aronov | On translational motion planning of a convex polyhedron in 3-space[END_REF]. This has led to the study of algorithms to compute approximations to Minkowski sums in R 3 [START_REF] Agarwal | Penetration depth of two convex polytopes in 3D[END_REF][START_REF] Guo | Optimal accurate Minkowski sum approximation of polyhedral models[END_REF][START_REF] Varadhan | Accurate Minkowski sum approximation of polyhedral models[END_REF]. In this paper, we show how to approximate the Minkowski sum of two convex polytopes in R d in near-optimal time. Theorem 2. Given a parameter ε > 0 and two polytopes A, B ⊂ R d each of size n (given either using a point or halfspace representation), it is possible to construct an ε-approximation of A ⊕ B of size

O(1/ε (d-1)/2 ) in O(n log 1 ε + 1/ε (d-1)/2+α
) time, where α is an arbitrarily small positive constant. The output representation can be either point-based or halfspace-based, irrespective of the input representations.

Width

Define the directional width of a set S of n points to be the directional width of conv(S). The width of S is the minimum over all directional widths. The maximum over all directional widths is equal to the diameter of S. Both problems can be approximated using the ε-kernel of S. After successive improvements [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Agarwal | Farthest neighbors, maximum spanning trees and related problems in higher dimensions[END_REF][START_REF] Arya | Better ε-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ε-kernels[END_REF][START_REF] Barequet | Efficiently approximating the minimum-volume bounding box of a point set in three dimensions[END_REF][START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF], algorithms to compute ε-kernels and to ε-approximate the diameter in roughly O(n + 1/ε d/2 ) time have been independently discovered by Chan [START_REF] Chan | Applications of Chebyshev polynomials to low-dimensional computational geometry[END_REF] and the authors [START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF]. Somewhat surprisingly, these works offer no improvement to the running time to approximate the width [START_REF] Agarwal | Approximating extent measures of points[END_REF][START_REF] Chan | Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus[END_REF][START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF][START_REF] Duncan | Efficient approximation and optimization algorithms for computational metrology[END_REF][START_REF] Yu | Practical methods for shape fitting and kinetic data structures using coresets[END_REF], which Chan [START_REF] Chan | Applications of Chebyshev polynomials to low-dimensional computational geometry[END_REF] posed as an open problem. The fastest known algorithms date from over a decade ago and take roughly O(n + 1/ε d-1 ) time [START_REF] Chan | Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus[END_REF][START_REF] Chan | Faster core-set constructions and data-stream algorithms in fixed dimensions[END_REF].

Agarwal et al. [START_REF] Agarwal | Penetration depth of two convex polytopes in 3D[END_REF] showed that the width of a convex body K is equal to the minimum distance from the origin to the boundary of the convex body K ⊕ (-K) (see Figure 1(b)). Using Theorem 2, we can approximate the width by computing an ε-approximation of K ⊕ (-K) represented as the intersection of halfspaces and then determining the closest point to the origin among all bounding hyperplanes. The following presents this result.

Theorem 3. Given a set S of n points in R d and an approximation parameter ε > 0, it is possible to compute an ε-approximation to the width of S in O(n log 1 ε + 1/ε (d-1)/2+α ) time, where α is an arbitrarily small positive constant.

Techniques

Our algorithms and data structure are based on a data structure defined by a hierarchy of Macbeath regions [START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF][START_REF] Arya | Optimal approximate polytope membership[END_REF], which answers approximate directional width queries in polylogarithmic time. First, we show how to use this data structure as a black box to answer approximate polytope intersection queries by transforming the problem to a dual setting and performing a multidimensional convex minimization. Next, we show how to use approximate polytope intersection queries to compute ε-approximations of the Minkowski sum. The approximation to the width follows directly.

Since we only access the input polytopes through a data structure for approximate directional width queries, our results apply in much more general settings. For example, we could answer in polylogarithmic time whether the Minkowski sum of two polytopes (preprocessed independently) approximately intersects a third polytope. Our techniques are also amenable to other polytope operations such as intersection and convex hull of the union, as long as the model of approximation is defined accordingly.

The preprocessing time of the approximate directional width data structure we use is

O(n log 1 ε + 1/ε (d-1)/2+α
), for arbitrarily small α > 0. If this preprocessing time is reduced in the future, the complexity of our algorithms becomes equal to the preprocessing time plus O((1/ε (d-1)/2 ) polylog 1 ε ).

Preliminaries

In this section we present a number of results, which will be used throughout the paper. The first provides three basic properties of Minkowski sums. The proof can be found in standard sources on Minkowski sums (see, e.g., [START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF]).

Lemma 4. Let A, B ⊂ R d be two (possibly infinite) sets of points. Then:

(a) A ∩ B = ∅ if and only if O ∈ A ⊕ (-B), where O is the origin. (b) conv(A ⊕ B) = conv(A) ⊕ conv(B). (c) For all nonzero vectors v, width v (A ⊕ B) = width v (A) + width v (B).
Next, we recall a recent result of ours on answering directional width queries approximately [START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF], which we will use as a black box later in this paper. Given a set S of n points in a constant dimension d and an approximation parameter ε > 0, the answer to the approximate directional width query for a nonzero query vector v consists of a pair of points p, q ∈ S such that width v ({p, q}) ≥ (1 -ε) width v (S).

Lemma 5. Given a set S of n points in R d and an approximation parameter ε > 0, there is a data structure that can answer ε-approximate directional width queries with query time O(log 2 1 ε ), space O(1/ε (d-1)/2 ), and preprocessing time O(n log 1 ε + 1/ε (d-1)/2+α ).

Fattening

Existing algorithms and data structures for convex approximation often assume that the bodies have been fattened through an appropriate affine transformation. In the context of multiple bodies, this is complicated by the fact that different fattening transformations may be needed for the two bodies or their Minkowski sum. In this section we explore this issue. Consider a convex body K in d-dimensional space R d . Given a parameter 0 < γ ≤ 1, we say that K is γ-fat if there exist concentric Euclidean balls B and B , such that B ⊆ K ⊆ B , and radius(B)/ radius(B ) ≥ γ. We say that K is fat if it is γ-fat for a constant γ (possibly depending on d, but not on ε or K). For a centrally symmetric convex body C, the body obtained by scaling C about its center by a factor of λ is called the λ-expansion of C.

Let K be a convex body. We say that a convex body C is a λ-sandwiching body for K if C is centrally symmetric and C ⊆ K ⊆ C , where C is a λ-expansion of C. John [START_REF] John | Extremum problems with inequalities as subsidiary conditions[END_REF] proved tight bounds for the constant λ of a λ-sandwiching ellipsoid. This ellipsoid is referred to as the John ellipsoid. Lemma 6. For every convex body K in R d , there exists a d-sandwiching ellipsoid. Furthermore, if K is centrally symmetric, there exists a √ d-sandwiching ellipsoid.

It is an immediate consequence of this lemma that for any convex body K there exists an affine transformation T such that T (K) is (1/d)-fat. Any affine transformation that maps the John ellipsoid into a Euclidean ball will do. The following lemma generalizes this to hyperrectangles (see also ). Lemma 7. For every convex body K in R d , there exists a (d 3/2 )-sandwiching hyperrectangle.

Proof. Let E denote the d-sandwiching ellipsoid for K, described in Lemma 6. By elementary geometry, there exists a √ d-sandwiching hyperrectangle R for E. We claim that R is a (d 3/2 )-sandwiching hyperrectangle for K. To prove this claim, observe that

R ⊆ E ⊆ R and E ⊆ K ⊆ E , where R is the √ d-expansion of R and E is the d-expansion of E. Letting R denote the d-expansion of R , it is easy to see that E ⊆ R . It follows that R ⊆ E ⊆ K ⊆ E ⊆ R . Since R is the d-expansion of R and R is the √ d-expansion of R, it follows that R is the (d 3/2
)-expansion of R. This completes the proof.

Next, let us consider fattening in the context of multiple bodies. The next two lemmas follow from elementary geometry and properties of Minkowski sums. Lemma 8. Let C 1 and C 2 be λ-sandwiching bodies for K 1 and K 2 , respectively. Then

C 1 ⊕ C 2 is a λ-sandwiching body for K 1 ⊕ K 2 .
Lemma 9. Let K be a convex body. Given a λ-sandwiching polytope for K of constant complexity, we can compute a γ-fattening affine transformation T for K in constant time, where γ = 1/(λ √ d).

Proof. Let C denote the given λ-sandwiching polytope for K. Recalling that λ-sandwiching polytopes are centrally symmetric, by Lemma 6 we can find a √ d-sandwiching ellipsoid E for C. As C has constant complexity, we can determine E in O(1) time. In O(1) time, we can also find the affine transformation T that converts E into a Euclidean ball. We claim that

T (K) is γ-fat for γ = 1/(λ √ d). To prove this claim, observe that E ⊆ C ⊆ E and C ⊆ K ⊆ C , where E is the √ d-expansion of E and C is the λ-expansion of C. Letting E denote the λ-expansion of E , it is easy to see that C ⊆ E . It follows that E ⊆ C ⊆ K ⊆ C ⊆ E . Since E is the √ d-expansion of E and E is the λ-expansion of E , it follows that E is the λ √ d-expansion of E.
Thus T (K) is contained between Euclidean balls T (E) and T (E ), whose radii differ by a factor of λ √ d, which proves the lemma.

We conclude by showing that we can maintain a small amount of auxiliary information for any collection of convex bodies in order to determine the fattening transformation for the Minkowski sum of any two members of this library. We refer to the data structure for approximate directional width queries from Lemma 5 together with the additional information to determine the fattening transformation as the augmented data structure for approximate directional width queries.

Lemma 10. Consider any finite collection of convex polytopes in R d , and let γ = 1/d 2 . It is possible to store information of constant size with each polytope such that in constant time we can compute a γ-fattening affine transformation for the Minkowski sum of any two polytopes from the collection. This information can be computed in time proportional to the size of the input polytope.

Proof. At preprocessing time, we store the λ-sandwiching hyperrectangles R i for each K i , where λ = d 3/2 . By Lemma 7, such hyperrectangles exist and they can be computed in time proportional to the size of the input polytope [START_REF] Chazelle | On linear-time deterministic algorithms for optimization problems in fixed dimension[END_REF].

Suppose we want to compute a γ-fattening affine transformation for K i ⊕ K j , where K i and K j are the result of applying (possibly different) affine transformations to K i and K j , respectively. Let C i and C j be the polytopes of constant complexity obtained by applying the corresponding affine transformations to R i and R j , respectively. Clearly, C i and C j are λ-sandwiching polytopes for K i and K j , respectively. Thus, by Lemma 8, C i ⊕ C j is a λ-sandwiching polytope for K i ⊕ K j . Note that this polytope has constant complexity and can be computed in constant time. Applying Lemma 9, we can use this polytope to compute a γ-fattening affine transformation for

K i ⊕ K j in constant time, where γ = 1/(λ √ d) = 1/d 2 .
The previous lemma holds more generally even when each of the polytopes are subject to any non-singular affine transformation and to the Minkowski sum of a constant number of polytopes.

Projective Duality and Width

Our algorithm for approximating the directional width of a point set is based on a projective dual transformation, which maps points into hyperplanes and vice versa. Each primal point p = (p 1 , . . . , p d ) ∈ S is mapped to the dual hyperplane p * :

x d = p 1 x 1 + • • • + p d-1 x d-1 -p d .
Each primal hyperplane is mapped to a dual point in the same manner. This dual transformation has several well-known properties [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF]. For example, the points in the lower convex hull of S map to the hyperplanes in the upper envelope.

Let H be a set of n hyperplanes in R d . Given a point r ∈ R d-1 , the thickness of H at r, denoted thick r (H) is defined as follows. Given r ∈ R d-1 and t ∈ R, let (r, t) denote the point in R d resulting by concatenating r and t. For the sake of illustration, we think of the d-th coordinate axis as being the vertical axis. Let r = (r, t 1 ) and r = (r, t 2 ). We define thick r (H) as the maximum difference t 2 -t 1 for points r , r in the hyperplanes in H. In other words, the thickness is the vertical distance between the intersection of the vertical line defined by r with the upper and lower envelopes of H. The following relates width and thickness.

Lemma 11. Consider two points p, q ∈ R d and a vector v = (v 1 , . . . , v d-1 , -1). Let p * , q * denote the dual hyperplanes and v 1,d-1 = (v 1 , . . . , v d-1 ). We have

thick v 1,d-1 ({p * , q * }) = v width v ({p, q}).
Proof. Given vectors u and v, let u•v denote the standard inner product. Assume without loss of generality that p p d ) and q = (q 1 , . . . , q d ). The dual hyperplanes are

• v ≥ q • v. Clearly, v is nonzero, so width v ({p, q}) = (p • v -q • v)/ v . Let p = (p 1 , . . . ,
p * : x d = p 1 x 1 + • • • + p d-1 x d-1 -p d and q * : x d = q 1 x 1 + • • • + q d-1 x d-1 -q d . If we set x 1 , . . . , x d-1 = v 1,d-1 we have t 2 = (p 1 , . . . , p d-1 ) • v 1,d-1 -p d and t 1 = (q 1 , . . . , q d-1 ) • v 1,d-1 -q d . Therefore thick v 1,d-1 (H) = t 2 -t 1 = (p 1 , . . . , p d-1 ) • v 1,d-1 -p d -((q 1 , . . . , q d-1 ) • v 1,d-1 -q d ) = p • v -q • v = v width v ({p, q}).

Approximate Convex Intersection

In this section, we will prove Theorem 1 for the case when the input polytopes are represented by points. Assume that we are given two polytopes A and B in the point representation. The objective is to preprocess A and B individually such that we can efficiently answer approximate intersection queries for A and B (or more generally for affine transformations of A and B).

Given a convex body K, ε > 0, and a point p, an ε-approximate polytope membership query is defined as follows. If p ∈ K, the answer is "yes," if p / ∈ K ε , the answer is "no," and otherwise, either answer is acceptable. Our strategy to answer approximate intersection queries is based on reducing them to approximate polytope membership queries. This reduction is presented in the following lemma, which is a straightforward generalization of Lemma 4(a) to an approximate context. The proof follows from standard algebraic properties of Minkowski sums and the observation that K ε can be expressed as K ⊕ ε 2 (K ⊕ -K). Lemma 12. Let A, B ⊂ R d be two polytopes and ε > 0. Determining the ε-approximate intersection of A and B is equivalent to determining the ε-approximate membership of O ∈ A ⊕ (-B).

Proof. We begin by establishing the useful identity A ε ⊕ B ε = (A ⊕ B) ε . By basic properties of Minkowski sums (commutativity and distributivity) we have B)) ε , implying that the approximate membership query returns "no."

A ε ⊕ B ε = A ⊕ ε 2 (A ⊕ -A) ⊕ B ⊕ ε 2 (B ⊕ -B) = (A ⊕ B) ⊕ ε 2 (A ⊕ B) ⊕ -(A ⊕ B) = (A ⊕ B) ε , width v (S) O O * x 1 , . . . , x d-1 = v 1 , . . . , v d-1 thick v 1 ,...,v d-1 (S * ) y -y F v (a) (b)
The previous lemma relates approximate polytope intersection with an approximate membership of the origin in a polytope (Figure 2(a)). Determining whether the origin lies within the convex hull of a set of points S is a classic problem in computational geometry, which can be solved by linear programming. However, we are interested in a faster approximate solution that does not compute S explicitly. We cannot afford to preprocess an approximate polytope membership data structure for A ⊕ (-B) for each pair A and B, since the number of such pairs is quadratic in the number of input polytopes. Instead, we preprocess each input polytope individually, and we show next how to efficiently answer approximate polytope membership queries for A⊕(-B) by using augmented data structures for approximate directional width queries for A and B as black boxes.

Lemma 13. Given augmented data structures for answering ε-approximate directional width queries for polytopes A and B, we can answer ε-approximate membership queries for A ⊕ (-B) using O(polylog 1 ε ) queries to these data structures.

Proof. Without loss of generality, we may translate space so that the query point coincides with the origin O. Let K = A ⊕ (-B), and let S be K's vertex set. (Note that K and S are not explicitly computed.)

The problem of determining whether O ∈ K is invariant to scaling and rotation about the origin. It will be helpful to perform some affine transformations that will guarantee certain properties for K. First, we apply Lemma 10 to fatten K and then apply a uniform scaling about the origin so that K's diameter is Θ [START_REF] Agarwal | Polygon decomposition for efficient construction of Minkowski sums[END_REF]. By fatness, K has a λ-sandwiching ball of radius r = Θ(1). If the origin either lies within the inner ball or outside the outer ball, then the answer is trivial. Otherwise, let ∆ = 2λr be the diameter of the outer ball. We may apply a rotation about the origin so that the center of this ball lies on the positive x d axis at a point (0, . . . , 0, β). Again, this scaling and rotation can be computed in constant time using the augmented information. It follows that the coordinates of the points of S have absolute values at most ∆ = Θ(1).

In summary, there exists an affine transformation computable in constant time such that after applying this transformation, the query point lies at the origin, K = conv(S) is sandwiched between two concentric balls of constant radii centered at c = (0, . . . , 0, β), where 0 < β ≤ ∆ = O(1), and K's vertex set S is contained within [-∆, ∆] d . It is an immediate consequence that width v (K) = Θ(1) for all directions v, and hence it suffices to answer the membership query to an absolute error of Θ(ε).

Lemma 4(c) implies that we can answer ε-approximate width queries for K as the sum of two εapproximate width queries to A and B. Therefore, our goal is to determine approximately if O ∈ K using only approximate width queries to A and B. In order to do this, we look at the projective dual problem in which each point p = (p 1 , . . . , p d ) ∈ S is mapped to the hyperplane p * : The dual problem can be solved exactly by computing the minimum value y of the x d -coordinate in the upper envelope and testing whether y > 0. In the primal, the value of y corresponds to the negated x dcoordinate of the intersection of a facet F of the lower convex hull of K and a vertical line passing through the origin (see Figure 2). Let F 's supporting hyperplane be denoted by

x d = p 1 x 1 + • • • + p d-1 x d-1 -p d . Let S *
x d = w 1 x 1 + • • • + w d-1 x d-1 -w d .
Since K is sandwiched between two concentric balls of constant radii whose common center lies on this vertical line, it follows from simple geometry that this supporting hyperplane cannot be very steep. In particular, there exists α = O(1) such that w i ∈ [-α, α], for i = 1, . . . , d -1. In the dual, this means that the minimum value y is attained at a point whose first d -1 coordinates all lie within [-α, α]. In approximating y, we will apply directional width queries only for directional vectors v = (v 1 , . . . , v d ) whose first d -1 coordinates lie within [-α, α] and v d = -1. Thus, v = O(1).

By Lemma 11, the duals of two points p, q ∈ S returned by an exact directional width query width v (K) in the primal for a vector v = (v 1 , . . . , v d-1 , -1) correspond to the two dual hyperplanes in the upper and lower envelopes of S * that intersect the vertical line x i = v i for i = 1, . . . , d -1. Since queries are only applied to directions v where v = O(1) and since width v (K) = Θ(1) for all directions v, it follows from Lemma 11 that a relative error of ε in the directional width implies an absolute error of O(ε) in the corresponding thickness. We can think of the upper envelope of S * as defining the graph of a convex function over the domain [-α, α] d-1 . Since S ⊂ [-∆, ∆] d , the slopes of the hyperplanes in S * are similarly bounded, and therefore this function has bounded slope. It follows that, for an appropriate ε = Θ(ε), we can compute this function to an absolute error of ε at any (v 1 , . . . , v d-1 ) by performing an (ε )-approximate directional width query on K for v = (v 1 , . . . , v d-1 , -1). To complete the proof, it suffices to show that with O(polylog 1 ε ) such queries, it is possible to compute an absolute ε-approximation to y. We do this in the next section.

Convex Minimization

The following lemma shows how to use binary search to solve a one-dimensional convex minimization problem approximately (see Figure 3 Proof. First, we present the recursive algorithm used to determine the value x . If b -a < ε, then since the function has bounded slope, we simply return x = a, as a valid answer.

Otherwise, we start by trisecting the interval [a, b] and evaluate f ε (x) at the four endpoints x 1 , x 2 , x 3 , x 4 of the subintervals (see Figure 3(a)). Let m denote the value i that minimizes f ε (x i ), breaking ties arbitrarily. To simplify the boundary cases, let x 0 = a and x 5 = b. We then invoke our algorithm recursively on the interval [x m-1 , x m+1 ] and store the value returned as x . We return the value x among the two values x m , x that minimizes f ε (x).

Since the length of the interval reduces by at least one third at each iteration, the number of recursive calls and therefore evaluations of f ε (•) is O(log((b -a)/ε)). Next, we show that f (x ) -f (x * ) = O(ε). By the convexity of f we have

f (x) ≥ f (x m+1 ) + 3(x -x m+1 )(f (x m+1 ) -f (x m ))/(b -a), for x ≥ x m+1 . Using that |f (x) -f ε (x)| ≤ ε, we have f (x) ≥ f ε (x m+1 ) -ε + 3(x -x m+1 )(f ε (x m+1 ) -f ε (x m ) -2ε)/(b -a), for x ≥ x m+1 . Since f ε (x m ) ≤ f ε (x m+1 ), we have f (x) ≥ f ε (x m ) -ε -6ε(x -x m+1 )/(b -a), for x ≥ x m+1 .
For x inside the interval [a, b] we have |x -x m+1 | ≤ b -a, and therefore

f (x) ≥ f ε (x m ) -7ε, for x m+1 ≤ x ≤ b.
The same argument is used to bound the case of a ≤ x ≤ x m-1 , obtaining

f (x) ≥ f ε (x m ) -7ε, for x / ∈ [x m-1 , x m+1 ].
Either the minimum of f (x) is inside the interval [x m-1 , x m+1 ] or not. If it is not, then the previous inequality shows that f ε (x m ) provides a good approximation, regardless of the value returned in the recursive call. If the minimum is inside the interval [x m-1 , x m+1 ], then the recursive call will provide a value result by an inductive argument.

We are now ready to extend the result to arbitrary dimensions. Proof. The minimum f (x * ) can be written as

f (x * ) = min x∈[a,b] d f (x) = min x1∈[a,b] min x∈[a,b] d-1 f (x 1 , x).
Note that if f (x) is a convex function with bounded slope, then so is the function g

: [a, b] → R (see Figure 3(b)) defined as g(x 1 ) = min x∈[a,b] d-1 f (x 1 , x).
The proof is based on induction on the dimension d. Since d is a constant, the number of induction steps is also a constant. The base case of d = 1 follows from Lemma 14. By the induction hypothesis, we can solve the (d -1)-dimensional instance to obtain a function g (x 1 ) such that

|g(x 1 ) -g (x 1 )| = O(ε).
Using Lemma 14 for the function g (•), we obtain a value x with f (x ) -f (x * ) = O(ε).

For the number of function evaluations t(d) for a given dimension d we have

t(1) = O(log((b -a)/ε)) and t(k) = t(1) • t(k -1).
The recurrence easily solves to the desired

t(d) = O(log d ((b -a)/ε)).
By applying Lemma 15 to the dual problem defined in the proof of Lemma 13 (where f is the graph of the upper envelope of S * and [a, b] = [-α, α]) with the augmented data structure from Lemma 5, we obtain Theorem 1 for the case when the input polytopes are represented by points. We will consider the case when the input polytopes are represented by halfspaces at the end of the next section.

Minkowski Sum Approximation

In this section, we will prove Theorems 2 and 3, as well as Theorem 1 for the case when the input polytopes are represented by halfspaces. Assume that we are given two polytopes A and B in the point representation, and we have computed the augmented approximate directional width data structures from Lemma 5 for each polytope. The objective is to obtain an ε-approximation of the Minkowski sum A ⊕ B of size O(1/ε (d-1)/2 ) using these data structures. Our approach is to fatten A ⊕ B using Lemma 10 and then apply Dudley's construction [START_REF] Dudley | Metric entropy of some classes of sets with differentiable boundaries[END_REF] in order to obtain an approximation with O(1/ε (d-1)/2 ) halfspaces.

For completeness, we start by describing Dudley's algorithm. Let K ⊂ [-1, 1] d be a fat polytope of constant diameter. Dudley's algorithm obtains an ε-approximation represented by halfspaces as follows. Let D be a ball of radius 2 √ d centered at the origin. (Note that K ⊂ D.) Place a set W of Θ(1/ε (d-1)/2 ) points on the surface of D such that every point on the surface of D is within distance O( √ ε) of some point in W . For each point w ∈ W , let w be its nearest point on the boundary of K. We call these points samples. For each sample point w , take the supporting halfspace passing through w that is orthogonal to the vector from w to w. The approximation is defined as the intersection of these halfspaces (see Figure 4(a)).

Bronshteyn and Ivanov [START_REF] Bronshteyn | The approximation of convex sets by polyhedra[END_REF] presented a similar construction. Instead of approximating K by halfspaces, Bronshteyn and Ivanov's construction approximates K as the convex hull of the aforementioned set of samples 1 (see Figure 4(b)). In both constructions it is possible to tune the constant factors so that closest point queries need only be computed to within an absolute error of Θ(ε).

An approximate closest point query between a polytope K and a point p within constant distance from K can be reduced to computing an ε-approximation to the smallest radius ball centered at p that intersects K. This can be solved through binary search on the radius of this ball, where each probe involves determining whether K intersects a ball of some radius centered at p. Notice that the data structure for approximate polytope intersection from Section 3 only accesses the bodies through approximate directional width queries, besides the initial fattening transformation. By Lemma 4(c), given two preprocessed bodies A and B, we can answer directional width queries on A ⊕ B through directional width queries on A and B individually. (In the case of a ball, no data structure is required.) Therefore, we can test intersection with a Minkowski sum A ⊕ B, as long as we have augmented approximate directional width data structures for both A and B.

In order to establish Theorem 2 for the case when the input polytopes are represented by points, we apply the aforementioned binary search to simulate Dudley's construction. Each sample is obtained after O(log 1 ε ) ε-approximate polytope intersection queries. The total running time is dominated by the preprocessing time of Lemma 5. Note that the output polytope may be represented by either points or halfspaces according to whether we use Dudley's or Bronshteyn and Ivanov's algorithm. To show that the input polytopes may be represented by halfspaces, we show how to efficiently convert between the two representations.

Lemma 16. Given an approximation parameter ε > 0 and a polytope K ⊂ R d of size n (given either using a point or halfspace representation), we can obtain an ε-approximation of size O(1/ε (d-1)/2 ) (in either representation, independent of the input representation) in O(n log 1 ε + 1/ε (d-1)/2+α ) time, where α > 0 is an arbitrarily small constant.

Proof. The case when the input is represented by points is a trivial case of Theorem 2, where B = {O}. For the alternative case, it suffices to obtain an ε-approximation of the polar polytope after fattening. (For details see Lemma 2.9 of the full version of [START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF].)

We remind the reader that Agarwal et al. [START_REF] Agarwal | Penetration depth of two convex polytopes in 3D[END_REF] showed that the width of a convex body K is equal to the minimum distance from the origin to the boundary of the convex body K ⊕ (-K). To obtain Theorem 3, we compute Dudley's approximation of K ⊕ (-K) and then we determine the closest point to the origin among the O(1/ε (d-1)/2 ) bounding hyperplanes of the approximation.

Figure 2 :

 2 Figure 2: (a) Primal problem of determining if O ∈ conv(S). (b) Dual problem of determining if the horizontal hyperplane O * is between the upper and lower envelopes.

Figure 3 :

 3 Figure 3: (a) One-dimensional convex minimization. (b) Higher-dimensional convex minimization.

  (a)). Lemma 14. Let a, b ∈ R and ε ∈ R+ be real parameters. Let f : [a, b] → R be a convex function with bounded slope and f ε : [a, b] → R be a function with |f (x) -f ε (x)| ≤ ε for all x ∈ [a, b]. Let x * ∈ [a, b] be the value of x that minimizes f (x). It is possible to determine a value x with f (x ) -f (x * ) = O(ε) after O(log((b -a)/ε)) evaluations of f ε (•) and no evaluation of f (•).

Lemma 15 .

 15 Let a, b ∈ R and ε ∈ R+ be real parameters. Let f : [a, b] d → R for a constant dimension d be a convex function with bounded slope and f ε : [a, b] d → R be a function with |f (x) -f ε (x)| ≤ ε for all x ∈ [a, b] d . Let x * ∈ [a, b] d be the value of x that minimizes f (x). It is possible to determine a value x with f (x ) -f (x * ) = O(ε) after O(log d ((b -a)/ε)) evaluations of f ε (•) and no evaluation of f (•).

Figure 4 :

 4 Figure 4: (a) Dudley's and (b) Bronshteyn and Ivanov's polytope approximations.

Dudley's construction yields an outer approximation and Bronshteyn and Ivanov's yields inner approximation, but it is possible to convert both to the other type through standard techniques. For details, see Lemma

2.8 of the full version of[START_REF] Arya | Near-optimal ε-kernel construction and related problems[END_REF].

* Research supported by the Research Grants Council of Hong Kong, China under project number 16200014. † Research supported by the European Research Council under ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). ‡ Research supported by NSF grant CCF-1618866.