Pascal Auscher

Andreas Axelsson

Andreas Axelsson Remarks

REMARKS ON MAXIMAL REGULARITY

Keywords: 1991 Mathematics Subject Classification. Primary 47D06; Secondary 35K90, 47A60 maximal regularity, weighted estimates, abstract Cauchy problem, Kato's inequality, fractional powers, Cotlar's lemma

come

In honour of H. Amann's birthday

Weighted estimates for the maximal regularity operator

Assume -A is a densely defined, closed linear operator, generating a bounded analytic semigroup {e -zA , | arg z | < δ}, 0 < δ < π/2, on a Hilbert space H. Equivalently, A is sectorial of type ω(A) = π/2 -δ. Let D(A) denote its domain. The maximal regularity operator is defined by the formula

M + f (t) = t 0 Ae -(t-s)A f (s) ds.
This operator is associated to the forward abstract evolution equation u(t) + Au(t) = f (t), t > 0; u(0) = 0 as for appropriate f , Au(t) = M + f (t). An estimate on M + f in the same space as f gives therefore bounds on u and Au separately. See Section 2.

The integral defining M + f converges strongly in H for each f ∈ L 2 (0, ∞; dt, D(A)) and t > 0. The estimate Ae -(t-s)A ≤ C(t -s) -1 following from the analyticity of the semigroup shows that the integral is singular if one only assumes f (s) ∈ H. The maximal regularity operator is an example of a singular integral operator with operator-valued kernel. The celebrated theorem by de Simon [START_REF] De Simon | Un'applicazione della teoria degli integrali singolari allo studio delle equazioni differenziali lineari astratte del primo ordine[END_REF] asserts Theorem 1.1. Assume -A generates a bounded holomorphic semigroup in H. The operator M + , initially defined on L 2 (0, ∞; dt, D(A)), extends to a bounded operator on L 2 (0, ∞; dt, H).

Motivated by boundary value problems for some second order elliptic equations, we proved in [START_REF] Auscher | Weighted maximal regularity and solvability of non-smooth elliptic systems[END_REF] the following result.

Theorem 1.2. Assume -A generates a bounded holomorphic semigroup in H and furthermore that A has bounded holomorphic functional calculus, then M + , initially defined on L 2 c (0, ∞; dt, D(A)), extends to a bounded operator on L 2 (0, ∞; t β dt, H) for all β ∈ (-∞, 1). The proof given there uses the operational calculus defined in the thesis of Albrecht [START_REF] Albrecht | Functional calculi of commuting unbounded operators[END_REF]. It used as an assumption that A has bounded holomorphic functional calculus as defined by McIntosh [START_REF] Mcintosh | Operators which have an H ∞ functional calculus[END_REF]. Under this assumption estimates of integral operators more general than the maximal regularity operator, with operator-kernels defined through functional calculus of A, were proved and gave other useful informations to understand also the case β = 1 needed for the boundary value problems. However, not all generators of bounded analytic semigroups have a bounded holomorphic functional calculus. (See [START_REF] Mcintosh | Operators of type ω without a bounded H ∞ functional calculus[END_REF], and Kunstmann and Weis [START_REF] Kunstmann | Maximal Lp-regularity for parabolic equations, Fourier multiplier theorems and H ∞ -functional calculus[END_REF]Section 11] for a list of equivalent conditions.) So if we only consider the maximal regularity operator, it is natural to ask whether one can drop the assumption on bounded holomorphic functional calculus in Theorem 1.2. It is indeed the case and as we shall see the proof is extremely simple assuming we know Theorem 1.1.

Theorem 1.3. Let -A be the generator of a bounded analytic semigroup on H. Then M + , initially defined on L 2 c (0, ∞; dt, D(A)), extends to a bounded operator on L 2 (0, ∞; t β dt, H) for all β ∈ (-∞, 1).

The subscript c means with compact support in (0, ∞).

Set |||f (t)||| 2 = ∞ 0 f (t)
= ∞ 0 h(u) du u < ∞, then ||| ∞ 0 U (t, s)f (s) ds s ||| ≤ C|||f (s)|||.
Proof of Theorem 1.3. Let β < 1. For β = 0, this is Theorem 1.1. Assume β = 0 and set α = β/2. Observe that

M + f (t) L 2 (t β dt,H) = t α M + f (t) L 2 (dt,H) .
We have, with f α (s) = s α f (s),

t α M + f (t) = M + (f α )(t) + t 0 Ae -(t-s)A (t α -s α )f (s) ds.
For the first term apply Theorem 1.1. For the second, write

t 0 Ae -(t-s)A (t α -s α )f (s) ds L 2 (dt,H) = ||| ∞ 0 U (t,
U (t, s) ≤ C |t α -s α | |t -s| s 1/2-α t 1/2 , s < t.
It is easy to see that it is on the order of (s/t) 1/2-max(α,0) as s < t. We conclude by applying Schur's lemma.

Let M -f (t) = ∞ t Ae -(s-t)A f (s) ds.
This operator is associated to the backward abstract evolution equation

v(t) -Av(t) = f (t), t > 0; v(∞) = 0 as for appropriate f , Av(t) = -M -f (t).
Corollary 1.4. Assume that -A generates a bounded analytic semigroup on H. Then M -, initially defined on L 2 c (0, ∞; dt, D(A)), extends to a bounded operator on L 2 (0, ∞; t β dt, H) for all β ∈ (-1, ∞).

Proof. Observe that the adjoint of M -in L 2 (0, ∞; t β dt, H) for the duality defined by

L 2 (0, ∞; dt, H) is M + in L 2 (0, ∞; t -β dt, H) associated to A * and apply Theorem 1.3.
We next show that the range of β is optimal in both results.

Theorem 1.5. For any non zero -A generating a bounded analytic semigroup on H and

β ≥ 1, M + is not bounded on L 2 (0, ∞; t β dt, H) and M -is not bounded on L 2 (0, ∞; t -β dt, H). Proof. It suffices to consider M -. Since A = 0, R(A), the closure of the range of A, contains non zero elements. As R(A) ∩ D(A) is dense in it, pick u ∈ R(A) ∩ D(A), u = 0, and set f (t) = u for 1 ≤ t ≤ 2 and 0 elsewhere. Then f ∈ L 2 c (0, ∞; dt, D(A)) and f ∈ L 2 (0, ∞; t -β dt, H) with f (t) L 2 (0,∞;t -β dt,H) = c β u < ∞. For t < 1, one has M -f (t) = (e -(1-t)A -e -(2-t)A )u,
which converges to (e -A -e -2A )u in H when t → 0. We claim that (e -A -e -2A )u = 0 so

M -f (t) 2 L 2 (0,∞;t -β dt,H) ≥ 1 0 (e -(1-t)A -e -(2-t)A )u 2 dt t β = ∞.
To prove the claim, we argue as follows. Assume it is 0, then e -2A u = e -A u so that an iteration yields e -nA u = e -A u for all integers n ≥ 2. If n → ∞, e -nA u tends to 0 in H because u ∈ R(A). Thus e -A u = 0 and it follows that e -tA u = e -(t-1)A e -A u = 0 for all t > 1. The analytic function z → e -zA u is thus identically 0 for | arg z | < δ. On letting z → 0, we get u = 0 which is a contradiction.

We have seen that M -cannot map L 2 (0, ∞; t -1 dt, H) into itself and that it seems due to the behavior of M -f (t) at t = 0 for some f . We shall make this precise and general: under a further assumption on A which we introduce next, we define M -:

L 2 (0, ∞; t -1 dt, H) → L 2 loc (0, ∞; dt, H) and show that controlled behavior at 0 of M -f guarantees M -f ∈ L 2 (0, ∞; t -1 dt, H).
We begin by writing whenever

f ∈ L 2 c (0, ∞; dt, D(A)) and denoting f -1/2 (s) = s -1/2 f (s), M -f (t) -e -tA ∞ 0 Ae -sA f (s) ds = t 1/2 M -(f -1/2 )(t) + 2t t Ae -(s-t)A (s 1/2 -t 1/2 )s 1/2 f (s) ds s + ∞ 2t A(e -(s-t)A -e -(s+t)A )(s 1/2 -t 1/2 )s 1/2 f (s) ds s - ∞ 2t Ae -(s+t)A t 1/2 s 1/2 f (s) ds s - 2t 0 Ae -(s+t)A sf (s) ds s .
The right hand side is seen to belong to L 2 (0, ∞; t -1 dt, H) with an estimate C|||f (s)||| using Theorem 1.1 for the first term and Schur's lemma for the other four terms. Hence, by density, the right hand side defines a bounded linear operator M -on L 2 (0, ∞; t -1 dt, H). Also, the integral

∞ 0 Ae -sA f (s) ds is defined as a Bochner integral in H whenever f ∈ L 2 c (0, ∞; dt, H). Thus, by density of D(A) in H, one can set for f ∈ L 2 c (0, ∞; dt, H), (1)
M -f (t) := M -f (t) + e -tA ∞ 0 Ae -sA f (s) ds in L 2 loc (0, ∞; dt, H).
Let E be the space of f ∈ L 2 (0, ∞; t -1 dt, H) such that the integrals R δ Ae -sA f (s) ds converge weakly in H as δ → 0 and R → ∞. Then the above equality extends to f ∈ E. Assuming, in addition, that A * satisfies the quadratic estimate [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF] |||sA * e -sA * h||| ≤ C h H for all h ∈ H,

we have E = L 2 (0, ∞; t -1 dt, H). Indeed, for all f ∈ L 2 (0, ∞; t -1 dt, H) and h ∈ H, (3)
∞ 0 (sAe -sA f (s), h) ds s ≤ |||f (s)||| |||sA * e -sA * h||| |||f (s)||| h H
and the weak convergence of the truncated integrals follows easily. Thus, the right hand side of (1) makes sense for all f ∈ L 2 (0, ∞; t -1 dt, H) under (2) and this defines M -f . Moreover, it follows from (3) that ( 4) sup

τ >0 1 τ 2τ τ M -f (t) 2 H dt ≤ C|||f (s)||| 2 .
Then remark that (5) lim

τ →0 1 τ 2τ τ M -f (t) dt = ∞ 0
Ae -sA f (s) ds in H, as the corresponding limit for M -f is 0 and e -tA → I strongly when t → 0. All this yields the following result.

Proposition 1.6. Let -A be the generator of a bounded analytic semigroup in H and assume that the quadratic estimate (2) holds for A * . Then (1) defines M -f ∈ L 2 loc (0, ∞; dt, H) with estimates (4) and limit (5) for all f ∈ L 2 (0, ∞; t -1 dt, H). In particular,

M -f ∈ L 2 (0, ∞; t -1 dt, H) if and only if lim τ →0 1 τ 2τ τ M -f (t) dt = 0.
The last condition defines a closed subspace of L 2 (0, ∞; t -1 dt, H) and there is a constant C such that for all f in this subspace

M -f (t) L 2 (0,∞;t -1 dt,H) ≤ C f (t) L 2 (0,∞;t -1 dt,H) .
Note that (2) holds if A has bounded holomorphic functional calculus by McIntosh's theorem [START_REF] Mcintosh | Operators which have an H ∞ functional calculus[END_REF]. Remark 1.7. For M + , the analysis is not that satisfactory (for β = 1). One can show similarly that

M + f (t) -Ae -tA ∞ 0 e -sA f (s) ds L 2 (0,∞;tdt,H) ≤ C f (t) L 2 (0,∞;tdt,H) provided f ∈ L 2 c (0, ∞; dt, D(A)).
If the quadratic estimate (2) holds for A, this allows to extend M + to the space {f ∈ L 2 loc (0, ∞; dt, H);

∞ 0 e -sA f (s) ds converges weakly in H}. However, there is no simple description of this space.

Applications to the abstract Cauchy problem

In this section, we assume throughout that -A generates a bounded analytic semigroup in H.

Let f ∈ L 2 loc (0, ∞; dt, H). We say that u is a weak solution to u(t) +

Au(t) = f (t), t > 0, if u ∈ L 2 loc (0, ∞; dt, H), (6)
sup 0<τ <1 1 τ 2τ τ u(s) H ds < ∞ and for all φ ∈ C 1 c (0, ∞; H) ∩ C 0 c (0, ∞; D(A * )), ( 7
) ∞ 0 (u(s), -φ(s) + A * φ(s)) ds = ∞ 0 (f (s), φ(s)) ds.
The notion of weak solution here differs from the one in Amann's book [2, Chapter 5] called weak L p,loc solution (p ∈ [1, ∞]) specialized to p = 2. We assume a uniform control through (6) near t = 0 and assume φ compactly supported in (0, ∞) in ( 7) instead of specifying the initial value at t = 0 and taking φ compactly supported in [0, ∞) in [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF].

Lemma 2.1. Let β ∈ (-∞, 1) and f ∈ L 2 (0, ∞; t β dt, H). Then (8) v(t) = t 0 e -(t-s)A f (s) ds satisfies (1) v ∈ C 0 ([0, ∞); H) and for all t > 0, v(t) 2 ≤ Ct 1-β t 0 s β f (s) 2 ds, (2) v is a weak solution to u(t) + Au(t) = f (t), t > 0, (3) Av(t) = M + f (t) in L 2 loc (0, ∞; dt, H), and v(t) L 2 (0,∞;t β dt,H) + Av(t) L 2 (0,∞;t β dt,H) ≤ C f (t) L 2 (0,∞;t β dt,H) .
Here, by M + we mean the bounded extension to L 2 (0, ∞; t β dt, H).

Proof. The inequality in (1) follows from the uniform boundedness of the semigroup and Cauchy-Schwarz inequality, and this shows that the integral defining v(t) norm converges in H, thus infering continuity on [0, ∞), and also [START_REF] Kunstmann | Maximal Lp-regularity for parabolic equations, Fourier multiplier theorems and H ∞ -functional calculus[END_REF]. To check [START_REF] Merdy | The similarity problem for bounded analytic semigroups on Hilbert space[END_REF], it suffices to change order of integration and calculate. The equality M + f = Av is proved by duality against a φ as in [START_REF] Merdy | The similarity problem for bounded analytic semigroups on Hilbert space[END_REF] since such φ form a dense subspace in L 2 c (0, ∞; dt, H). Finally, the inequalities in (3) are consequences of Theorem 1.3.

We now state that all weak solutions have an explicit representation and a trace at [START_REF] Merdy | Similarities of ω-accretive operators[END_REF]. In particular, t → u(t) can be redefined on a null set to be C 0 ([0, ∞); H) with trace h at t = 0. This immediately implies the following existence and uniqueness results.

t = 0. Proposition 2.2. Let β ∈ (-∞, 1) and f ∈ L 2 (0, ∞; t β dt, H). Let u be a weak solution to u(t) + Au(t) = f (t), t > 0. Then, there exists h ∈ H such that (9) u(t) = e -tA h + v(t) in L 2 loc (0, ∞; dt, H), with v defined by
Corollary 2.3. Let u 0 ∈ H. The initial value problem u(t) + Au(t) = 0, t > 0, with lim τ →0 1 τ 2τ τ u(t) dt = u 0 in H, has a unique weak solution given by u(t) = e -tA u 0 for almost every t > 0. In particular, up to redefining t → u(t) on a null set, u ∈ C ∞ (0, ∞; D(A)) and is a strong solution.

Corollary 2.4. Let β ∈ (-∞, 1) and f ∈ L 2 (0, ∞; t β dt, H). The initial value problem u(t) + Au(t) = f (t), t > 0, with lim τ →0 1 τ 2τ τ u(t) dt = 0 in H, has a unique weak solution given by v defined by (8), up to redefining t → u(t) on a null set.

Proof of Lemma 2.2. Define η(s) to be the piecewise linear continuous function with support [1, ∞), which equals 1 on (2, ∞) and is linear on (1, 2). Let t > 0. For 0 < ǫ < t/4 and s > 0, let η ǫ (t, s) := η(s/ǫ)η((t -s)/ǫ). For the first term, using e -(t-s)A -e -tA ≤ Cs/t from analyticity and ( 6), one sees that (

(t) = e -(t-τ )A h ǫ (τ ) for all t ≥ τ . Thus, h ǫ (t)-h ǫ ′ (t) H ≤ 1 b -a b a e -(t-τ )A (h ǫ (τ )-h ǫ ′ (τ )) H dτ ≤ C b a h ǫ (τ ) -h ǫ ′ (τ ) 2 H dτ 1/2
, when t > b. Hence, since (a, b) is arbitrary, h ǫ (t) converges in H to h(t) for each t > 0. Thus, for any φ 0 ∈ H and t > 0, we have

(h ǫ , e -tA * φ 0 ) = (h ǫ (t), φ 0 ) → (h(t), φ 0 ).
Since (h ǫ ) ǫ<1 is a bounded sequence in H by ( 6) and the elements e -tA * φ 0 , t > 0, φ 0 ∈ H, form a dense set of H, we infer that h ǫ has a weak limit in H. Calling h this weak limit we have (h, e -tA * φ 0 ) = (h(t), φ 0 ), hence h(t) = e -tA h as desired. Summarizing, we have obtained -e -tA h + u(t) = v(t) in L 2 (a, b; H) for all 0 < a < b < ∞. Thus, u agrees almost everywhere with the continuous function t → v(t) + e -tA h which has limit h at t = 0.

Remark 2.5. The only time analyticity is used in this proof is in [START_REF] Mcintosh | Operators of type ω without a bounded H ∞ functional calculus[END_REF]. If we had incorporated the existence of an initial value as in [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF] in our definition of a weak solution then analogous proposition and corollaries would hold for all generators of bounded C 0semigroups.

A proof of maximal regularity via Kato's inequality for fractional powers

There are many proofs of the de Simon's theorem, via Fourier transform or operational calculus, and various extensions to Banach spaces. We refer to [6, Section 1].

Here, we wish to provide a proof using "almost orthogonality arguments" (Cotlar's lemma), and Kato's inequality for fractional powers [5, Theorem 1.1] which we recall for the reader's convenience. uA * 2 e -(s-t+u)A * vA 2 e -(s-τ +v)A ds.

This time we use the bound A * α A -α ≤ C(α) for α ∈ (0, 1/2) to obtain, if τ ≤ t, As Kato's inequality holds for all α ∈ (-1/2, 1/2), the argument above can be used to prove that M + is bounded on L 2 (0, ∞; t β dt, H) but for β ∈ (-1, 1). We leave details to the reader.

K(u,v) (t, τ ) ≤ C(u/v) α v 1+α (τ -t + v) 2+α and if t ≤ τ , K(u,v) (t, τ ) ≤ C(u/v) α u 1-α (t -τ + u) 2-α . So,

Let φ 0 e

 0 ∈ H be any boundary function, and choose φ(s) := η ǫ (t, s)e -(t-s)A * φ 0 ∈ Lip c (0, ∞; D(A * )) as test function (by approximating η ǫ (t, s) by a smooth function, this can be done). A calculation yields-1 ǫ 2ǫ ǫ e -(t-s)A u(s), φ 0 ds + 1 ǫ 2ǫ ǫ e -sA u(t -s), φ 0 ds = ∞ 0 η ǫ (t, s)e -(t-s)A f (s), φ 0 dsand since this is true for arbitrary φ 0 ∈ H and η ǫ has compact support, we deduce thatu(t -s) ds = ∞ 0 η ǫ (t, s)e -(t-s)A f (s) ds.Now, we let ǫ → 0 as follows. First, η ǫ (t, s) tends to the indicator function of (0, t) so that the right hand side is easily seen to converge to v(t) in H for any fixed t > 0 by dominated convergence. Fix now 0 < a < b < ∞ and integrate in t ∈ (a, b) the left hand side. Remark that 1 sA u(t) dsdt converges to b a u(t) dt in H. Substracting this quantity from the second term in the right hand side and using u ∈ L 2 loc (0, ∞; H), Lebesgue's theorem yields -sA (u(t -s) -u(t)) ds -s) -u(t)2 H dsdt → 0.

( 0 K

 0 If τ ≤ t, bound a(s) by a(τ ) and getK (u,v) (t, τ ) ≤ Ca(τ )v -α = C(u/v) α u 1-α (t -τ + u) 2-α . K (u,v) (t, τ ) + K (u,v) (τ, t) ) dt ≤ C(u/v) α .By Schur's lemma we obtain T u T * v ≤ C(u/v) α when u ≤ v. We now turn to estimate T * u T v . By symmetry under taking adjoints again, it is enough to assume u ≤ v. We obtain(T * u T v )(g)(t) = ∞ (u,v) (t, τ )g(τ ) dτ where K(u,v) (t, τ ) = ∞ max(t,τ )

  u,v) (t, τ ) + K(u,v) (τ, t) ) dt ≤ C(u/v) αand by Schur's lemma, T u T * v ≤ C(u/v) α when u ≤ v.

We thank Alan McIntosh for discussions on the topic of this short note.

Theorem 3.1. Let A be closed and maximal accretive. For any 0 ≤ α < 1/2, the operators A α and A * α have same domains and satisfy [START_REF] Simard | Counterexamples concerning powers of sectorial operators on a Hilbert space[END_REF] A * α f ≤ tan π(1 + 2α) 4 A α f .

If, moreover, A is injective then A α A * -α extends to a bounded operator on H for -1/2 < α < 1/2.

Maximal accretive means that Re(Au, u) ≥ 0 for every u ∈ D(A) and (λ -A) -1 is bounded whenever Reλ < 0. Note that [START_REF] Simard | Counterexamples concerning powers of sectorial operators on a Hilbert space[END_REF] holds true with different constants for operators which are similar to a closed and maximal accretive operator. Assume A is sectorial of type w(A) < π/2 and injective. Le Merdy showed in [START_REF] Merdy | The similarity problem for bounded analytic semigroups on Hilbert space[END_REF] that A is similar to a maximal accretive operator if and only if A has bounded imaginary powers (i.e. A it is bounded for all t ∈ R). (See also [START_REF] Merdy | Similarities of ω-accretive operators[END_REF] for a more general result and [START_REF] Simard | Counterexamples concerning powers of sectorial operators on a Hilbert space[END_REF] for explicit examples.) But, following earlier works of Yagi [START_REF] Yagi | Coïncidence entre des espaces d'interpolation et des domaines de puissances fractionnaires d'opérateurs[END_REF], McIntosh showed in his seminal paper [START_REF] Mcintosh | Operators which have an H ∞ functional calculus[END_REF] that A has bounded imaginary powers if and only if A has a bounded holomorphic functional calculus. (See [START_REF] Kunstmann | Maximal Lp-regularity for parabolic equations, Fourier multiplier theorems and H ∞ -functional calculus[END_REF]Section 11] for extensive discussions with historical notes.) So proving maximal regularity (i.e. Theorem 1.1) assuming maximal accretivity is the same as proving maximal regularity assuming bounded holomorphic functional calculus. Nevertheless, this direct argument below could be of interest.

Proof of Theorem 1.1 under further assumption of maximal accretivity. Since Ae -(t-s)A annihilates N(A), the null space of A, we may assume g(s) ∈ R(A) for all s > 0. Alternately, we may factor out the null space of A and assume that A is injective, which we do (A is sectorial, so H splits topologically as N(A) ⊕ R(A)).

Then one can write g(s) = ∞ 0 uAe -uA g(s) du u and so we have the representation of M + as

By Cotlar's lemma (see [12, Chapter VII]) it is enough to show in operator norm on

x < ∞ to conclude that M + is bounded on L 2 (0, ∞; H) with norm less than or equal to C. We show that for all α ∈ (0, 1/2) one can take h(x) = C α min (x α , x -α ) .

We begin with

where

uA 2 e -(t-s+u)A vA * 2 e -(τ -s+v)A * ds.

We turn to estimate the operator norm on H of K (u,v) (t, τ ) for fixed (t, τ ). (Recall we fixed (u, v) with u ≤ v.) Since A is maximal accretive and injective, we have A α A * -α ≤ C(α) for α ∈ (0, 1/2). So we write


Jean-Daniel Boissonnat
email: boissonn@sophia.inria.fr

Sylvain Lazard
email: lazard@sophia.inria.fr

A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles Extended abstract

In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and nal con gurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two con gurations, avoiding the obstacles, and with the further constraint that, on each C 2 piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al. 1]) and present a polynomial-time exact algorithm to solve this problem.

Introduction

In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane, SBC path for short. More precisely, given prescribed initial and nal con gurations (i.e. positions and orientations) and a set of obstacles in the plane, we want to compute a shortest C 1 path joining those two con gurations, avoiding the obstacles, and with the further constraint that, on each C 2 piece 1 , the radius of curvature is at least 1. This question appears in many applications and goes back to Markov who studied the problem for joining pieces of railways. More recently, a great deal of attention has been paid to this question in the context of non-holonomic robot motion planning 2, [START_REF] Barraquand | Nonholonomic mobile robots and optimal maneuvering[END_REF][START_REF] Jacobs | Planning smooth paths for mobile robots[END_REF][START_REF] Kedem | On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles[END_REF][START_REF] Latombe | A fast path-planner for a car-like indoor mobile robot[END_REF][START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Laumond | Finding collision-free smooth trajectories for a non-holonomic mobile robot[END_REF][START_REF] Laumond | A motion planner for nonholonomic mobile robots[END_REF][START_REF] Li | Nonholonomic Motion Planning[END_REF][START_REF] Wang | Approximation algorithms for curvature constrained shortest paths[END_REF][START_REF] Wilfong | Motion planning for an autonomous vehicle[END_REF]. A robot is said to be non-holonomic if some kinematics constraints locally restricts the authorized directions for its velocity. A typical example of a non-holonomic robot is that of a car : assuming 1 As we will see below, the optimal path is piecewise C 2 .

no slipping of the wheels on the ground, the velocity of the midpoint between the two rear wheels of the car is always tangent to the car axis. Though the problem considered in this paper is one of the simplest instances of non-holonomic motion planning, it is still far from being well understood.

Even in the absence of obstacles, the problem is not easy. Dubins 10] proved that any SBC path takes one of the following forms CSC or CCC, where C means a circular arc of radius 1 and S a straight line segment. The proof in Dubins's paper is quite long and intricate. Recently, a much simpler proof has been obtained using the Minimum Principle of Pontryagin (a central result in Control Theory) 6, 22] and a complete characterization of SBC paths has also been established 7].

The problem becomes much harder in the presence of obstacles. By basic theorems in Control Theory, there exists a SBC path amidst obstacles and joining two given con gurations as soon as there exists a BC path, i.e. a (not necessarily optimal) C 1 path joining the two given con gurations, avoiding the obstacles and where the radius of curvature is everywhere (where it is de ned) greater than or equal to 1. Moreover, a SBC path is a nite concatenation of subpaths either contained in the boundary of some obstacle or joining two obstacle edges (considering the initial and the nal con gurations as point obstacles); each subpath joining two obstacle edges is a Dubins' path, i.e. a path of type CSC or CCC. Computing a shortest path seems however a formidable task. Even if we remove the requirement for the path to be a shortest one and look for a BC path (instead of a SBC path), no polynomial-time algorithm is known. [START_REF] Dubins | On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents[END_REF], Fortune and Wilfong present an exact algorithm that can decide if a BC path exists but does not generate the path in question. This algorithm runs in time and space that is exponential with respect to the number n of corners of the environment and the number of bits used to specify the positions of the corners. By the remark above, this algorithm can also decide if a SBC path exists.

For computing SBC paths, only approximate algorithms have been proposed in the literature. Jacobs and Canny 12] discretize the problem and calculate a path that approximates the shortest one in time O(n 2 ( n+L " ) log n + (n+L) 2 " 2 ), where " describes the closeness of the approximation and L is the total edge length of the obstacle boundaries. Very recently, Wang and Agarwal 23] improved on this result and proposed an algorithm whose time complexity is O( n 2 " 2 log n), and thus does not depend on L. In another recent paper, Agarwal et al. 1] have considered a restricted class of obstacles, the so-called moderate obstacles : an obstacle is said to be moderate if it is convex and if its boundary is a di erentiable curve whose radius of curvature is everywhere greater than or equal to 1. This restriction is quite strong but valid in many practical situations. Under the assumption that all the obstacles are disjoint and moderate, Agarwal et al. show that an approximate SBC path can be computed in O(n 2 log n + 1=") time.

In this paper, we consider also the case of moderate obstacles (in a more restrictive sense than Agarwal et al.) and present a polynomial-time algorithm to compute a SBC path (assuming that the roots of some polynomials of bounded degree can be computed in constant time). To the best of our knowledge, this is the rst polynomial-time exact algorithm for a non trivial instance of the problem.

The paper is organized as follows. In Section 2, we introduce some notations and show that the problem reduces to nding an Euclidean shortest path when the initial and the nal positions are su ciently far away and also su ciently far from the obstacles. In the following Sections 3, 4 and 5 we show that SBC paths belong to a nite family. In Section 6, we describe an algorithm that computes an optimal path between two given con gurations.

Preliminaries

First, we give some de nitions and notations. Let be a set of obstacles. In this paper, the obstacles are assumed to be disjoint and moderate. An obstacle is said to be moderate if it is convex and if its boundary is a di erentiable curve made of line segments and circular arcs of unit radius. For convenience and without real loss of generality, we assume that no two edges of the obstacles are parallel. A path that avoids the obstacles (i.e. that does not intersect the interior of the obstacles) is called free. In the sequel, a free SBC path is simply called an optimal path.

Let ! S = (S; ŨS ) and ! T = (T; ŨT ) be two con gurations (i.e. positions and orientations). Let P be an optimal path joining ! S to ! T . As mentioned in the introduction, P is a nite concatenation of O, C and S-segments; an O-segment is a maximal portion of P that coincides with the boundary of an obstacle; a C-segment is a maximal circular arc of unit radius that is not an O-segment; a S-segment is a maximal line segment, possibly on the boundary of some obstacle. To a path, we will associate the sequence of the types (O, C or S) of its segments. The rst and last segments are called terminal. A terminal segment is, in general, a C-segment; we denote it by C t . A C-segment (or a circle of unit radius) is denoted by The rst theorem shows that, when the initial and the nal positions are su ciently far away and also su ciently far from the obstacles, the optimal path is an Euclidean shortest path for an augmented set of obstacles.

C if it S T ŨS ŨT R S R T C L (S) C R (S) C L (T ) C R (T ) A I I 0 P C 0 S C 0 T Figure 1: Regions R S and
Let X be a point of P and Ũ the vector tangent to P at X. Let C L (X) (resp. C R (X)) be the unit circle tangent to P at X and lying on the left (resp. right) side of P (i.e. on the left side of the oriented line passing through X with direction Ũ). C L (X) is oriented counterclockwise and C R (X) is oriented clockwise. An arc of one of these circles will be oriented accordingly.

Let C 0 S (resp. C 0 T ) be the circle tangent to C L (S) and C R (S) (C L (T) and C R (T)) that does not intersect the ray (S; ŨS ) (the ray (T; ? ŨT )) (see Figure 1). Let R S (resp. R T ) be the shaded region limited by C L (S), C R (S) and C 0 S (C L (T), C R (T) and C 0 T ) in Figure 1.

Lemma 1 If R S and R T are disjoint and do not intersect the obstacles, P does not intersect the interior of R S nor that of R T .

Proof: We assume for a contradiction that P intersects the interior of R S . We consider rst the case where P does not intersect the interior of R T . As P is a path of bounded curvature, P intersects C L (S) or C R (S). Let I be the last intersection point (along P) between P and C L (S) C R (S); we assume, without loss of generality, that I 2 C L (S). Let I 0 be the last intersection point (along P) between P and R S and let II 0 be the part of P from I to I 0 . We denote by A the point common to C L (S) and C 0 S (see Figure 1).

First, we assume that I 6 = S. Let SI be the arc of C L (S), oriented as C L (S), that starts at S and ends at I. Let P 0 be the concatenation of SI and the part of P from I to T. P 0 is not a path of bounded curvature but it is shorter than P since the shortest path of bounded curvature from ! S to I (the orientation at I is not speci ed) is the arc SI 5]. Let P 00 be the path obtained by modifying P 0 as follows : if I 0 6 = I, then we replace the arc AI of C L (S) and II 0 by the circular arc AI 0 of C 0 S . The path P 00 is shorter than P 0 . Thus P 00 is shorter than P, avoids all the moderate obstacles, avoids R S by construction and R T because R S \ R T = ;. Hence, the Euclidean shortest path from S to T avoiding , R S and R T is shorter than P. That yields a contradiction because this Euclidean shortest path is a path of bounded curvature from ! S to ! T .

If I = S, the orientation of P at I can only be ŨS or ? ŨS since I is the last intersection point between P and C L (S) C R (S). But only the latter case can occur since otherwise, P would not be optimal. As, by de nition, I lies before I 0 along P, the part of P from (S; ŨS ) to I 0 is longer than the shortest Dubins' path from (S; ŨS ) to (S; ? ŨS ) which is a path of type CCC of length 2 + =3. Let SI 0 be the concatenation of the arc SA of C L (S) and the circular arc AI 0 , and let P 0 be the concatenation of SI 0 and the part of P from I 0 to T. As, the length of SI 0 is at most 2 , P 0 is shorter than P. We then get a contradiction as above.

Similar arguments hold if P intersects the interior of R T .

2

Theorem 2 If R S and R T are disjoint and do not intersect , P is the Euclidean shortest path from S to T avoiding and the two additional obstacles R S and R T . Proof: It follows from Lemma 1 that P is also the shortest path from ! S to ! T if we consider R S and R T as some other (moderate) obstacles. On the other hand, the Euclidean shortest path from S to T that avoids , R S and R T is a path of bounded curvature from (S; ŨS ) to (T; ŨT ). Hence, P is the Euclidean shortest path from S to T in the presence of the obstacles , R S and R T .

2 Corollary 3 A Dubins' path of type CCC between two congurations ! S and ! T is optimal only if the two regions R S and R T intersect.

In the rest of the paper, we will assume that Theorem 2 does not apply.

Characterization of the C-segments

We rst recall the following lemma mentionned in the introduction which follows from 10] or 6] : Lemma 4 Each subpath of an optimal path which has no point in common with the obstacles except possibly its two end points must be of type CCC or CSC. Proof: Consider rst an optimal subpath of type C t C CO where the O-segment is a circular arc. We use the same perturbation that Dubins used to reduce the length of CCCCpaths. It follows that the second or the third C-segments of C t C CO must be clamped by some obstacles. Hence, the third C-segment is anchored or both the second and the third C-segments are tangent to some obstacles.

Consider now an optimal subpath of type C t C CS and the two types of perturbation shown in Figure 2. Perturbation (a) has been used by Dubins to shorten the path and it can be shown, using the same kind of argument, that perturbation (b) shortens also the path. Thus, if the subpath is optimal, either the third C-segment is anchored or both the second and the third C-segments are tangent to some obstacles. Since a subpath of type CCCC cannot be optimal, we have shown that a subpath of type C t CC is either C

t C C or C t C C. 2
As, for a given set of obstacles, the number of anchored circles is nite, the number of the subpaths in Theorem 9 is nite except for the subpaths of type C C. The two following sections will show that the number of these subpaths is also nite. First, in Section 4, we will show that any non-terminal subpath of type C C of an optimal path is necessarily contained in a subpath of type XS C CSX 0 where X; X 0 2 fO; Cg. Then, in Section 5, we will show that, given X; X 0 and two obstacle edges, the number of subpaths of an optimal path of type XS C CSX 0 where the C-segments are tangent to the given obstacle edges is nite. The section is devoted to the proof of the following theorem :

O 1 O 2 4 cos ũ O 1 O 2 2 O 1 O 2 (d):
Theorem 10 Any non terminal subpath of type C C of an optimal path is necessarily contained in a subpath of type XS C CSX 0 where X; X 0 2 fO; Cg. The length of S-segment may be zero.

In the sequel, we will use the following notations. For a given subpath P, C i will denote the i-th C-segment of P, C i will denote the circle supporting C i and O i the center of C i (i 2 f1;2;3g).

We rst establish two lemmas and a proposition. Lemma 11 In a subpath of type CCS of an optimal path where the rst C-segment is not terminal, the length of the S-segment is smaller than 4 cos . Here = 6 ( ???! O 2 O 1 ; ? ! u ) and ũ is the direction of the S-segment (see Figure 3).

Proof: We omit the proof in this abstract but Figure 3 shows the di erent kinds of shortcuts we use if the length of the S-segment is greater than 4 cos . Because the obstacles are moderate, the obstacles cannot intersect the shortcuts.

2

We consider now subpaths of type CCSC. Lemma 12 In a subpath of type CCSC of an optimal path where the rst and the last C-segments are not terminal, the two C-segments adjacent to the line segment have the same orientation (clockwise or counterclockwise). Proof: We omit the proof but Figure 4 shows the shortcut we use when C 1 does not intersect C 3 and Figure 5 shows the shortcut we use when C 1 intersects C 3 .

O 1 O 2 O 3 C 0 C 1 C 2 C 3

O

0 O 1 O 3 O 2 C 1 C 2 C 3 O 2 C 2 O 3 O 1 C 1 C 3 (a): 2 (? =2; ? =6) (b):
2 (? =6; 0) Proof: By Lemma 5, the lengths of the rst and the last Csegments are greater than if they are not terminal. According to the two previous lemmas, the length of the S-segment is less than 4 cos and the two C-segments adjacent to the line segment have the same orientation. Then, as shown in Figure 6, it is possible to shorten the subpath. We omit the details of the proof. This section is devoted to the proof of the following theorem :

O 4 O 3 O 2 O 1 C 1 C 2 C 3 C 4
Theorem 14 Let X (resp. X 0 ) be a circular edge of some obstacle or an anchored circle, and let O and O 0 be two obstacle edges. Let X X, X 0 X 0 , C a C-segment tangent to O and C 0 a C-segment tangent to O 0 . The shortest subpath of type XS C C 0 SX 0 belong to a nite family.

Let P denote a subpath of type XS C C 0 SX 0 . The number of subpaths P where C or C 0 are anchored is nite; so we assume that neither C nor C 0 are anchored. Without loss of generality, we assume in the sequel that the path P is oriented counterclockwise on C and clockwise on C 0 as shown in Figure 7. We only consider the case where both obstacle edges O and O 0 are circular arcs; the other cases are simpler and omitted here.

We rst observe that P is optimal when some mechanical device is at equilibrium. This leads to an algebraic system of equations whose solutions correspond to potential equilibriums of the mechanical device. We then show that this system has a nite number of solutions. This is done as follows. Let E 1 = 0; : : : ; E r = 0 be the equations of the system where E 1 ; : : : ; E r are polynomials in the variables x 1 ; : : : ; x r . The resultant R(x 1 ; : : : ; x r?1 ) with respect to x r of two of the E i , say E 1 and E 2 , vanishes at x1 ; : : : ; xr?1 i there exists xr such that (x 1 ; : : : ; xr?1 ; xr ) is a common root of E 1 and E 2 4]. By cascading resultants on the polynomials E 1 ; : : : ; E r , we eliminate successively the indeterminates x r ; : : : ; x 2 and compute a univariate polynomial R(x 1 ). If (x 1 ; : : : ; xr ) is a solution of the system, R(x 1 ) = 0 converse is not necessarily true). Then we show that the univariate polynomial R(x 1 ) is not identically zero and that any value of the indeterminate x 1 determines the other indeterminates. It immediately follows that the considered algebraic system of equations has a nite number of roots. Unfortunately, computing such a polynomial R(x 1 ) exceeds the capabilities of the current computer algebra systems. However, we can compute the leading monomial of R(x 1 ) which is su cient to show that R(x 1 ) 6 0. O and O 0 and the two disks of unit radius supporting X and X 0 . The moving object D is the union of two tangent disks (corresponding to the circles C and C 0 ). We consider a rubber band of thickness zero attached on X and on X 0 and passing around C and C 0 (see Figure 7). The case we are interested in is when both mobile disks are tangent to the obstacles. The moving object D is subject to four forces ? ! F , ? ! F 0 , ? ! R and ? ! R 0 (see Figure 7). ? ! F and ? ! F 0 are the two forces, of equal norm F, exerted by the rubber band. ? ! R and ? ! R 0 are the reactions of the obstacles O and O 0 onto the mobile D.

! ' 0 ' 0 ? ! F ? ! R ? ! R 0 ? ! F 0 I 0 I O O 0 0 H 2h H 0 ! 0 0 2h 0 O C O 0 C 0 X X 0
We introduce the following notations (see Figure 7). Let C and C 0 be the circles supporting C and C 0 . I and I 0 are the centers of C and C 0 . H and H 0 are the centers of the circles supporting X and X 0 . O and O 0 are the centers of the circles (of unit radius) supporting O and O 0 . Let 2d be the length of OO 0 and let 2h and 2h 0 be the lengths of OH and O 0 H 0 respectively. In addition, let = 6 ( ? ! R ; ?! II 0 ), 0 = 6 ( ? ! R 0 ; ?! I 0 I), ' = 6 ( ?! II 0 ; ? ! F ), ' 0 = 6 ( ?! I 0 I; ? ! F 0 ), ! = 6 ( ??! OO 0 ; ??! OH) and ! 0 = 6 ( ??! O 0 O; ???! O 0 H 0 ). We rst establish a lemma that holds regardless of the nature of the obstacle edges O and O 0 .

Lemma 15 The moving object D is at an equilibrium only if : sin( 0 ? ) + sin 0 sin( + ') ? sin sin( 0 + ' 0 ) = 0 (1) Proof: The moving object D is at an equilibrium i the sum of the forces ? ! F , ? ! F 0 , ? ! R , ? ! R 0 and the sum of their moments is zero. Straightforward computations yield Equation 1. 2

We now establish a system of four equations in four indeterminates whose solutions correspond to potential equilibriums of the mechanical device : Lemma 16 The moving object D is at an equilibrium only if :

8 > > > > > < > > > > > :
sin( 0 ? ) + sin 0 sin( + ') ? sin sin( 0 + ' 0 ) = 0 2 cos + 2 cos 0 + 2 cos( 0 ? ) + 3 ? d 2 = 0 h sin(' ? !) + h sin( 0 + ' ? !)+ h sin( + ' ? !) ? d sin( + ') + d = 0 h 0 sin(' 0 ? ! 0 ) + h 0 sin( + ' 0 ? ! 0 )+ h 0 sin( 0 + ' 0 ? ! 0 ) ? d sin( 0 + ' 0 ) + 0 d = 0

(2) where (resp. 0 ) is zero if the path P has the same orientation on X and C (X 0 and C 0 ) and 1 otherwise. Proof: The rst equation of System 2 is given by Lemma 15. Let = 6 ? ! OI; ??! OO 0 ) and 0 = 6 ( ??! O 0 I 0 ; ??! O 0 O) (see Figure 7).

Considering the polygon OII 0 O 0 , we have :

0 ? 0 = ? 2 ] (3)
cos + cos( ? ) + cos 0 = d (4) sin ? sin( ? ) + sin 0 = 0

Considering in turn ((Eq4) 2 + (Eq5) 2 ), ((Eq4)sin ? (Eq5)cos ), ((Eq4)cos + (Eq5)sin ), ((Eq4)sin 0 ? (Eq5)cos 0 ) and ((Eq4)cos 0 + (Eq5)sin 0 ), we obtain : 2 cos + 2 cos 0 + 2 cos( 0 ? ) + 3 ? d 2 = 0 (6) d sin = sin ? sin( 0 ? ) [START_REF] Boissonnat | Shortest paths of bounded curvature in the plane[END_REF] d cos = 1 + cos + cos( 0 ? ) [START_REF] Bui | Shortest path synthesis for Dubins nonholonomic robot[END_REF] d sin 0 = sin 0 + sin( 0 ? ) [START_REF] Clarkson | Applications of random sampling in computational geometry[END_REF] d cos 0 = 1 + cos 0 + cos( 0 ? ) (10) Equation 6 is the second equation of System 2. We show how to compute the two other equations of System 2 for the possible orientations of X and X 0 . P has the same orientation on X and C (see Figure 7). Let = 6 ( ??! HO; ?! HI) and consider the triangle (OHI) : sin( + ') 2h = sin 2 As = + ' ? ? ! 2 ], we get : h sin( + ' ? ? !) ? sin( + ') = 0

That equation can be expanded with respect to , and simpli ed thanks to Equations 7 and 8 : h sin('?!)+h sin( 0 +'?!)+h sin( +'?!)?dsin( +') = 0 P has the same orientation on X 0 and C 0 .

0 ! ' 0 ' 0 ? ! F ? ! R ? ! R 0 ? ! F 0 I 0 I O O 0 0 H 2h H 0 ! 0 0 2h 0 O C C 0 O 0 X 0 X
Similarly as above, we obtain the following equations : h 0 sin( 0 + ' 0 ? 0 ? ! 0 ) ? sin( 0 + ' 0 ) = 0 h 0 sin(' 0 ? ! 0 ) + h 0 sin( + ' 0 ? ! 0 )+ h 0 sin( 0 + ' 0 ? ! 0 ) ? d sin( 0 + ' 0 ) = 0 P has opposite orientation on X and C (see Figure 8). Let = 6 ( ? ! F ; ?! IH) and consider the triangle (OHI) : sin( + ' + ) 2h = sin 2 = sin( + !) IH As = + ' + ? ? ! 2 ], we get : 2 sin( + !) = IH sin( + ' ? ? !) cos +IH cos( + ' ? ? !) sin 2h sin( + !) = IH sin( + ') cos + IH cos( + ') sin Eliminating cos from these two equations gives :

2 sin( + !) sin( + ') ? 2h sin( + !) sin( + ' ? ? !) = IH cos( + ' ? ? !) sin sin( + ') ?IH cos( + ') sin sin( + ' ? ? !)

We simplify this equation into :

2 sin( + !) sin( + ') ? 2h sin( + !) sin( + ' ? ? !) = IH sin sin( + !) As sin = 2=IH (see Figure 8), we have : sin( + !)(h sin( + ' ? ? !) ? sin( + ') + 1) = 0

We can assume that sin( + !) 6 = 0 because otherwise I lies on the straight line OH and the number of such paths is less than four. Thus, the moving object is at an equilibrium only if : h sin( + ' ? ? !) ? sin( + ') + 1 = 0 Similarly as above, we expand that equation with respect to and simplify it, thanks to Equations 7 and 8 :

h sin(' ? !) + h sin( 0 + ' ? !)+ h sin( + ' ? !) ? d sin( + ') + d = 0 P have opposite orientations on X 0 and C 0 .

Similarly as above, we obtain the following equations : h 0 sin( 0 + ' 0 ? 0 ? ! 0 ) ? sin( 0 + ' 0 ) + 1 = 0 h 0 sin(' 0 ? ! 0 ) + h 0 sin( + ' 0 ? ! 0 )+ h 0 sin( 0 + ' 0 ? ! 0 ) ? d sin( 0 + ' 0 ) + d = 0

That ends the proof of the lemma.

2

We now show that System 2 has a nite number of roots ( ; ; '; ' 0 ) (in (S 1 ) 4 ). It then follows that the moving object D has a nite number of equilibriums.

We expand each equation of System 2 and apply the variable substitution x = tan( =2), y = tan( 0 =2), z = tan('=2) and t = tan(' 0 =2). This yields an algebraic system consisting of four equations where x; y; z; t are the four indeterminates and sin !; cos !; d; h; h 0 ; l 0 are considered as six independent parameters. Let E i = 0 (i 2 f1;: : : ; 4g) denote the algebraic equation obtained from the i-th equation of System 2. We compute2 the resultant E 14 of E 1 and E 4 with respect to the inderminate t. E 14 can be written as 16(1 + y 2 )E 0 14 . We compute3 the resultant Q of E 0 14 and E 2 with respect to the inderminate y. We also compute the resultant T of E 2 and E 3 with respect to the inderminate y. Q and T are two polynomials where x and z are the indeterminates. Now, let R be the resultant of Q and T with respect to z. R is a uni-variate polynomial in the indeterminate x and we want to show that R(x) 6 0. Let Q = q 0 + q 1 z + : : : + q n z n ; q n 6 = 0; T = t 0 + t 1 z + : : : + t m z m ; t m 6 = 0;

where the q i and the t i are uni-variate polynomials in the variable x. The resultant R of Q and T with respect to z is the determinant of the (n + m) (n + m) Sylvester matrix of Q and T with respect to z 4] : q 0 q 1 . . . . . q n q 0 . . . . . q n?1 q n . . . . . . . . q 0 . . . . . q n t 0 t 1 . . t m?1 t m . . . . . . . . t 0 . . . t m The resultant R(x) is too big to be computed with existing computer algebra systems but we are able to compute its leading monomial. The polynomials q i appear in the rst m rows of the Sylvester determinant and the polynomials t i appear in the last n rows. Thus the degree of R with respect to x is at most m max i2f0;:::;ng degree(q i (x)) + n max i2f0;:::;mg degree(t i (x)) = 168: We replace in the Sylvester determinant each q i (x) by its monomial of highest degree if degree(q i (x)) = max i2f0;:::;ng degree(q i (x)) and by 0 otherwise, and each t i (x) by its monomial of highest degree if degree(t i (x)) = max i2f0;:::;mg degree(t i (x)) and by 0 otherwise. We then compute the determinant and obtain : 2 56 d 8 (d 2 ? 1) 32 h 16 (h 02 sin 2 ! 0 + (h 0 cos ! 0 ? d) 2 ) 4 (d 2 h 02 sin 2 ! 0 + (dh 0 cos ! 0 ? 1) 2 ) 4 x 168 When this monomial is not zero, its degree is 168 and so it is the leading monomial of R(x). Hence R(x) 0 only if d = 1 or h = 0 or (! 0 ; h 0 ) = (0; d) or (! 0 ; h 0 ) = (0; 1=d). h 6 = 0 since, otherwise P is of type X C C 0 SX 0 where X is a circular arc; the proof of Theorem 9 shows that P is optimal only if either C or C 0 is anchored which contradicts the assumption made at the beginning of the proof. If (! 0 ; h 0 ) = (0; d) or (! 0 ; h 0 ) = (0; 1=d) we replace ! 0 and h 0 by their value in Q and T. Then, we apply the same procedure as above and show that the leading monomial of R(x) is 2 72 d 16 (d 2 ? 1) 32 h 16 x 152

This leading monomial does not depend on whether h 0 = d or h 0 = 1=d and on the orientation of P on X and X 0 . Since the obstacles are disjoint, d 6 = 1 and R(x) 6 0 (in the case d = 1, it can also be shown that the number of roots of the system of equations is nite). Hence, the number of roots of System 2 is nite since any given value of x determines at most two triplets of values for the other indeterminates y, z and t (see Figure 7). It follows that the number of possible equilibriums of our mechanical device is nite. That ends the proof of Theorem 14.

Remark 17 As we have seen, the number of optimal subpaths of type XS C C 0 SX 0 is nite as soon as the number of roots of an algebraic system of four equations in four indeterminates is nite. We have shown that this is indeed the case for any choice of the parameters of the system (which represent the position of the edges X, X 0 , O and O 0 ). A weaker result can be obtained by simply choosing pseudo random values for the parameters. The fact that the number of roots of the system is nite for a pseudo random choice of the parameters implies that, with probability close to 1, the number of roots of the system is nite for almost all set of parameters. Moreover, by computing a Gr bner basis of the system for a pseudo random set of parameters, we can show that the number of roots of the system is at most 36 with probability close to 1 (instead of 336 as given by the computations above).

The algorithm

Let O 1 ; : : : ; O m be the disjoint moderate obstacles. We denote by S O the set of the obstacle edges and by n its size.

Let S and F be the initial and the nal point of the optimal path that we want to compute. By Theorems 9 and 10, any C-segment is either an anchored C-segment, or is adjacent to a terminal C-segment and to an anchored Csegment, or belongs to a subpath of type XS C CSX 0 where X; X 0 2 fO; Cg (the lengths of the S-segments being possibly zero).

The algorithm computes rst the set S C of all the maxi- mal free anchored arcs of circle. A maximal free anchored arc is a maximal arc of an anchored circle that does not intersect the interior of the obstacles. It will be simply called a free anchored arc in the sequel. We will also say for short that an arc (or a subpath) intersects an obstacle i it intersects the interior of the obstacle.

To each obstacle and for a given r, we associate a grown obstacle which is the Minkowski sum of the obstacle and of a disk of radius r. Let A r be the arrangement of the boundaries of these grown obstacles. A point is said of level i in A r if it belongs to the interior of i grown obstacles. The vertices of level 0 are simply the vertices of the boundary of the union of the grown obstacles. Because the obstacles are disjoint, there are O(n) such vertices by a result of Kedem et al. 14]. The same bound holds for the number of vertices of the k rst levels for any constant k by the random sampling theorem of Clarkson and Shor 8]. Lemma 18 The number of free anchored arcs is O(n) and these arcs can be computed in O(n logn) time.

Proof: A circle of unit radius is intersected by at most ve obstacles. Indeed, the obstacles are disjoint and moderate which implies that each one contains a circle of unit radius. The claim follows since there are at most ve pairwise disjoint circles of unit radius that may intersect a given circle of unit radius. It follows that any point is of level at most ve in A 1 . Hence, A 1 has linear size and can be computed in O(n log n) time by standard techniques.

Since the centers of the anchored circles are the vertices of A 1 and each anchored circle is intersected by at most ve obstacles, the lemma is proved.

2

Once the free anchored arcs have been computed, we compute the set S S of all the free line segments that are tangent to two arcs of S C S O .

Lemma 19 S S has size O(n 2 ) and can be computed in O(n 2 log n) time.

Proof: First, we compute all the free line segments tangent to two obstacles. Let us consider each obstacle in turn, say O 1 for concreteness. Let D be an oriented line of orientation tangent to O 1 . The set of commun points between O 1 and D is either a single point or a line segment; let P be either this single point or the middle point of this line segment. If D intersects O i (i = 2; : : : ; m), we call P i the point common to D and O i that is closer to P . Let f i ( ) be the algebraic length of P P i on the oriented line D .

Let E + (resp. E ? ) be the lower (upper) envelope of the functions f i that are positive (negative). As the obstacles are pairwise disjoint, f i ( ) 6 = 0 and f i ( ) 6 = f j ( ) for all and i 6 = j. It follows that E + and E ? can be computed in O(n log n) time. A line segment joining P to P i is free i ( ; f i ( )) belongs to E + or E ? . Moreover, a line segment P P i is tangent to O i i P i is an end-point of f i . Hence, computing the free line segments tangent to O 1 and another obstacle reduces to compute E + and E ? .

Repeating the above procedure for all the obstacles, we conclude that all the free line segments tangent to two obstacles can be computed in O(n 2 log n) time.

We now compute the free line segments tangent to a free anchored arc and to either an obstacle or another anchored free arc. Let C 1 ; : : : ; C p be the anchored free arcs. We consider in turn each free anchored arc, say C 1 for concreteness, and apply exactly the same procedure as above to compute the free line segments tangent to C 1 and to an obstacle. As above, these segments can be computed in O(n logn) time by computing the envelopes E + and E ? . It remains to compute the free line segments tangent to C 1 and to the other anchored free arcs C 2 ; : : : ; C p . We de ne a function g i involving C 1 and C i and similar to the function f i de ned above. To each end point of g i that lies between E + and E ? corresponds a free line segment tangent to C 1 and C i . Deciding if such an end point lies between E + and E ? can be done in O(log n) time by binary search once the envelopes have been computed. As the number of free anchored arcs is O(n) by Lemma 18, the free line segments tangent to C 1 and to another anchored free arc can be computed in O(n log n) time. Hence, the free line segments tangent to an anchored free arc and to either an obstacle or another anchored free arc can be computed in O(n 2 log n) time in total.

2 We consider now the subpaths of type C t C C and CCC t .

We compute the set S C of all the circular arcs that avoid the obstacles and are tangent to a terminal circle and to an anchored free arc. As there are O(n) anchored free arcs, this step can easily be done in O(n 2 ) time.

By Theorem 9, S C S O S S S C contains all the arcs potentially taken by an optimal path except the subpaths of type XS C CSX 0 . We consider, in turn, all the quadruplets (X; O;O 0 ; X 0 ) where X and X 0 are obstacle edges or anchored arcs, and where O and O 0 are two obstacle edges.

First, we compute the family of potential optimal subpaths of type XS C CSX 0 where X (resp. X 0 ) is an arc of X (X 0 ) and the two C-segments C C are tangent to respectively O and O 0 . In a second step, we will check whether or not these potential optimal subpaths intersect other obstacles.

By solving an algebraic system as described in the proof of Theorem 14, we compute the family of potential optimal subpaths of type XS C CSX 0 when none of the two Csegments tangent to O and O 0 is anchored. That step can be performed in constant time for each chosen quadruplet assuming that the roots of a polynomial of bounded degree can be computed in constant time. Hence the total time complexity of this step is O(n 4 ). We also compute the subpaths of type XS C CSX 0 and XS C CSX 0 . As the number of anchored C-segments is O(n), the total number of these subpaths is O(n 4 ) and they can be easily computed in O(n 4 ) time. It remains to compute the set S C C of those subpaths that avoid the obstacles.

Lemma 20 S C C can be computed in O(n 4 log n) time. Proof: We show that we can check in O(log n) time whether or not a given subpath of type XS C CSX 0 intersects the obstacles. We consider successively the case of an arc of circle and the case of a line segment.

As mentionned in the proof of Lemma 18, a circle of unit radius intersects at most ve obstacles. We can identify the obstacles that intersect the circle supporting a given arc C by locating in O(log n) time the center of this circle in the arrangement A 1 . It then remains to check if the arc C (not the whole circle) actually intersects one of the obstacles. Each such test can be done in O(log n) time since each obstacle has O(n) edges 9].

We describe now how to check if a line segment S of a subpath of type XS C CSX 0 intersects the obstacles. By Lemma 11, the length of S is at most 4. It follows that if S intersects an obstacle, each of its end points are contained in the obstacle grown by a disk of radius 4. As the obstacles are disjoint and moderate, a point can only be contained in g = O(1) 4 such grown obstacles : hence, arrangement A 4 has linear size and can be computed in O(n logn) time. We locate one endpoint of S in A 4 and nd the at most g obstacles that may intersect S. We consider in turn each of these obstacles and check if S indeed intersects the obstacle. This can be done in O(log n) Theorem 21 An optimal path amidst a set of disjoint moderate obstacles with n edges in total can be computed in O(n 4 log n) time. 4 g is the maximal number of disjoint disks of unit radius that can be packed in a disk of radius 6.

Improving the performances of the algorithm We now show that the time complexity of the algorithm can be reduced in most practical situations. This is a consequence of the fact that the subpaths of type C C can only be encountered near the endpoints of the path. Theorem 22 is a consequence of a result of Agarwal et al. A complete proof can be found in the full version of this paper.

Theorem 22 An optimal path contains at most two nonterminal C C-subpaths (i.e. subpaths of type C C where both C-segments are not terminal). Moreover, if an optimal path consists of four parts P 1 , P 2 , P 3 and P 4 in this order, where P 2 and P 3 are C-segments centered at O 2 and O 3 , then 8M 2 P 1 MO 3 3 or 8N 2 P 4 , NO 2 3. Theorem 23 Let P be an optimal path joining S to F. Any subpath of P of type XS C CSX 0 , where X; X 0 2 fO; Cg, is contained in one of the two disks of radius 9 centered at S or F.

Proof: This theorem follows from Theorem 22 and we use the notations introduced in this theorem. Let P 1 (resp. P 4 ) be the portion of P between S (resp. F) and the rst (resp. last) C in the considered subpath. From Theorem 22, we have 8M 2 P 1 MO 3 3 or 8N 2 P 4 NO 2 3. Assume without loss of generality that 8M 2 P 1 MO 3 3. Then, S and the whole subpath XS C C is included in the disk of radius 3 centered at O 3 . On the other hand, by Lemma 11, the length of the line segment preceding X 0 is smaller than 4. Therefore, S and the whole subpath XS C CSX 0 is included in a disk of diameter 3 + 2 p 5 + 1 < 9. Hence the subpath of type XS C CSX 0 is included in a disk of radius 9 centered at S. 2

It follows that we can improve the procedure that computes the subpaths of type XS C CSX 0 . Indeed, instead of considering all n 4 quadruplets (X; O; O 0 ; X 0 ), we can only consider those that intersect one of the disks of radius 9 centered at S and F. If k is the number of such quadruplets, the time complexity of the algorithm becomes O(n 2 log n + k 4 log k). In particular, if the length of any obstacle edge is bounded from below by some positive constant, then k = O(1).

Theorem 24 Given a set of disjoint moderate obstacles with n edges whose lengths are bounded from below by some positive constant. An optimal path between two con gurations amidst those obstacles can be computed in O(n 2 log n) time.

Final remarks and open questions

The geometric results and the algorithm hold even if the obstacles are not disjoint. However, the time-complexity increases since the number of anchored C-segments may be not linear.

In this paper, we have considered obstacles whose boundaries consist of line segments and circular arcs of unit radius.

It would be interesting to consider more general moderate obstacles (in the sense of Agarwal et al.) and, in particular, obstacles whose boundaries consist of line segments and circular arcs of radii greater than or equal to 1. The system of equations corresponding to the equilibriums of the mechanical device (see Section 5) is very similar to the one in Lemma 16. However, the computations exceed the capabilities of the current computer algebra systems 5 and we have not been able to apply techniques similar to those in Section 5.

Many other questions remain open. We mention three of them we plan to consider in near future : Can similar results be obtained for polygonal robots? Can similar results be obtained if backwards moves are allowed? (preliminary results in that direction can be found in 1, 6, 21]). How crucial is the moderate hypothesis?

Figure 2 :

 2 Figure 2: Length reducing perturbations for CCCS paths

Figure 3 :

 3 Figure 3: Shortcuts used in Lemma 11

Figure 4 :

 4 Figure 4: Shortcut used in Lemma 12 if C 1 does not intersect C 3

Figure 5 :

 5 Figure 5: Shortcut used in Lemma 12 if C 1 intersect C 3

Figure 6 :

 6 Figure 6: Shortcut used in Proposition 13 5 Bounding the number of subpaths of type C C

Figure 7 :

 7 Figure 7: Mechanical device where both obstacle edges are circular edges

Figure 8 :

 8 Figure 8: For the proof of Theorem 14

  time 9]. 2 By Theorems 9, S C S O S S S C S C C contains all the arcs potentially taken by an optimal path. Let G be the weighted graph whose nodes are the tangent points between two arcs of S C S O S S S C S C C and whose edges are the arcs of S C S O S S S C S C C . The nal step of the algorithm consists in searching a shortest path in this graph.

  R T is tangent to at least one obstacle. A C-segment (or a circle of unit radius) is called anchored and denoted by C either if it is tangent to at least two obstacles, or if it is tangent to at least one obstacle and adjacent to a terminal C-segment, or if it is terminal.

The proof of Theorem 10 now follows. Indeed, let us consider a subpath of type XS C CSX 0 , X 6 2 fO; Cg. As X is not terminal, Lemma 6 implies that the length of the rst S-segment of the subpath cannot be zero. Therefore, by Theorem 9, X is necessarily a C-segment tangent to some obstacle and following another C-segment X 1 . Then, by Proposition 13, X 1 is terminal and therefore, X is anchored by de nition. This contradicts our assumption and ends the proof of the theorem.

We used AXIOM on a Sun Sparc-10 4 72Mhz with 512MB of main memory. Notice that several polynomials considered here are two big to be computed with MAPLE.

This computation takes roughly eleven hours and the process exceeds 130MB.

Acknowledgments : The authors would like to thank the GDR MEDICIS (GDR CNRS 1026) for giving them the oportunity to use the machines of the GAGE group at Ecole Polytechnique.