Xavier Goaoc

Hyo-Sil Kim

Sylvain Lazard

BOUNDED-CURVATURE SHORTEST PATHS THROUGH A SEQUENCE OF POINTS USING CONVEX OPTIMIZATION *

Keywords: Path planning, Bounded curvature, Dubins path, Convex optimization. AMS subject classification. 68U05

We consider the problem of computing shortest paths having curvature at most one almost everywhere and visiting a sequence of n points in the plane in a given order. This problem is a sub-problem of the Dubins Traveling Salesman Problem and also arises naturally in path planning for point car-like robots in the presence of polygonal obstacles. We show that when consecutive waypoints are distance at least four apart, this question reduces to a family of convex optimization problems over polyhedra in R n .

1. Introduction. Path-planning problems involve computing feasible paths, possibly optimal for some criterion such as time or length, for a robot moving among obstacles. These problems are central in robotics and they have been widely studied; see, for instance, the books and survey papers [START_REF] Halperin | Robotics[END_REF][START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Lavalle | Planning Algorithms[END_REF][START_REF] Schwartz | Algorithmic motion planning in robotics[END_REF]. In its simplest form, path planning focuses on collision-free paths. However, robots generally come with physical limitations, such as bounds on the velocity, acceleration or curvature. Such differential constraints, called nonholonomic, restrict the geometry of the paths it can follow. Although there has been a considerable amount of work on nonholonomic motion planning in the robotics and control communities, relatively little work has been done, in comparison, from an algorithmic perspective.

In this paper, we study the path-planning problem for a car-like robot constrained to move in the forward direction, and whose turning radius is bounded from below by a positive constant, which can be assumed to be equal to one by scaling the space. In this context, the robot follows bounded-curvature paths, that is, differentiable curves whose curvature is constrained to be at most one almost everywhere. The first results on curvature-constrained shortest paths go back to 1957 when Dubins [START_REF] Dubins | On curves of minimal length with a constraint on average curvature, and prescribed initial and terminal positions and tangents[END_REF] proved that, in the plane without obstacles, bounded-curvature shortest paths consist of arcs of unit radius circles and straight line segments.

We consider the problem of computing a bounded-curvature shortest path that visits, in order, a given sequence p 1 , . . . , p n of n points in the plane (with no obstacles). This problem is a sub-problem of the Dubins Traveling Salesman Problem which has been substantially studied in the robotics literature, for instance, in the context of UAV (unmanned air vehicles) path planning (see discussion below). It is also related to the problem of path planning in the presence of polygonal obstacles, because, roughly speaking, such a shortest path is also a locally shortest path through a sequence of points in the absence of obstacles (see § 8).

Results. We show that a bounded-curvature shortest path through a sequence of n points can be computed by convex optimization, provided that any two consecutive points are distance at least 4 apart. More precisely, we show that the problem reduces to a family of n-dimensional convex optimization sub-problems, each over a convex polyhedral domain defined by at most 4n inequalities. The number of sub-problems is 2 n-2 in the worst case (Theorem 6.1). This combinatorial complexity is considerable but, in a sense, intrinsic to the problem since there may exist up to 2 n-2 bounded-curvature locally shortest paths visiting the sequence of points (see Figure 5.3). However, the division into sub-problems corresponds to a partition of the space of candidate shortest paths according to some geometric type, and fewer sub-problems can be considered by partially inferring the type of the global solution from the geometry of the point set. In particular, the number of sub-problems can be reduced to 2 k where k is the number of "sharp turns" in the polygonal path p 1 . . . p n (Theorem 7.2).

The state-of-the-art algorithms for computing bounded-curvature shortest paths through a sequence of points are fast, and often run in time linear in the number of waypoints, but they can only guarantee multiplicative-factor approximations of an optimum; the best factor that can currently be achieved is rather large, as it is 1.91 under the same distance assumption as above (see discussion below). Since convex optimization methods are known to be efficient in practice and allow for additive-factor approximations, our reduction appears to open an interesting alternative. Our results do, however, say little on the theoretical complexity of the problem since most convex optimization methods are notoriously hard to analyze (see § 8).

Bounded curvature path planning problems usually come in two flavors, with free or prescribed initial and final directions. Even if our presentation focuses on the free-direction setting, our reduction to convex optimization works for both variants. As a consequence, our techniques brings new insight on the problem of path planning in the presence of polygonal obstacles (see § 8). Some of our intermediate results are also interesting in their own rights, in particular our sufficient condition for a path to be a shortest CSC-path (Lemma 3.1).

Previous work. The study of bounded-curvature path planning started with Dubins' [START_REF] Dubins | On curves of minimal length with a constraint on average curvature, and prescribed initial and terminal positions and tangents[END_REF] proof that, in the plane without obstacles, any bounded-curvature shortest path is a concatenation of at most three arcs that are circular arcs of unit radius (C-segments) or line segments (S-segments). Moreover, such shortest paths are of type CCC or CSC, or a substring thereof. These types of paths are generally referred to as Dubins paths. A more direct proof of this result, using ideas from control theory, was presented later by Boissonnat et al. [START_REF] Boissonnat | Shortest paths of bounded curvature in the plane[END_REF] and Sussmann and Tang [START_REF] Sussmann | Shortest paths for the reeds-shepp car: A worked out example of the use of geometric techniques in nonlinear optimal control[END_REF], independently.

The problem of computing shortest paths of bounded curvature through an ordered sequence of points was, to our knowledge, first considered by Bui [START_REF] Bui | Planification de trajectoire pour un robot polygonal non-holonome dans un environnement polygonal[END_REF] in 1994. Bui's high-level approach was similar to ours, that is to argue that a shortest path corresponds to a minimum of a convex function; unfortunately, several of the proofs from [START_REF] Bui | Planification de trajectoire pour un robot polygonal non-holonome dans un environnement polygonal[END_REF] have serious gaps. Bui also showed that a path of minimal length corresponds to a solution of one of 2 n algebraic systems, each consisting of O(n) equations of bounded degree; even though this is totally impractical, this solution illustrates well the difficulty of the problem.

An approximate solution can easily be obtained by considering the points as given on-line: starting from p 1 by a line segment to p 2 , for i 2, the path from p 1 to p i can be extended by the shortest CS path starting from p i , with the same tangent, and ending in p i+1 . When any two consecutive points are at least distance 4 apart, this greedy approach yields a path whose length is less than 1.91 times that of the optimum. 1 Without lower bound on the distance between consecutive points the approximation factor of the greedy algorithm cannot be bounded. This was addressed in 2000 by Lee et al. [START_REF] Lee | Approximation of curvature-constrained shortest paths through a sequence of points[END_REF] who presented a linear-time approximation algorithm for computing a path that is at most 5.03 times longer than the optimal one; we note that when the distance between any two consecutive points is at least d > 2, the guarantee on the approximation factor improves to 1 + 2π d which is less than 2.58 for d = 4. The problem of computing shortest paths of bounded curvature through an unordered set of points, referred to as Dubins TSP, has also been studied [START_REF] Ma | Receding horizon planning for Dubins traveling salesman problems[END_REF][START_REF] Le Ny | On the curvature-constrained traveling salesman problem[END_REF][START_REF] Rathinam | A resource allocation algorithm for multivehicle systems with nonholonomic constraints[END_REF][START_REF] Savla | Traveling salesperson problems for the Dubins vehicle[END_REF]; see also [START_REF]The curvature-constrained traveling salesman problem for high point densities[END_REF] for a short survey. It is NPhard [START_REF] Le Ny | On the curvature-constrained traveling salesman problem[END_REF] and all proposed approximation algorithms are based on a discretization of the directions at the waypoints. The discretizations are, however, very rough: in essentially all cases, only one direction is chosen at each point. The stochastic version of this problem, in which the n waypoints are randomly distributed, has also been studied; see, e.g., [START_REF] Enright | UAV routing in a stochastic time-varying environment[END_REF][START_REF] Itani | On the stochastic TSP for the Dubins vehicle[END_REF][START_REF] Savla | Traveling salesperson problems for the Dubins vehicle[END_REF].

Boissonnat and Lazard [START_REF] Boissonnat | Convex hulls of bounded curvature[END_REF] also considered the related problem of computing the convex hull of bounded curvature of a set of points, that is the shortest bounded-curvature closed curve that encloses all the points. Here the path does not necessarily pass through every point. This simplifies the problem because it then reduces to computing the polygon of shortest perimeter whose vertices lie, in order, inside the unit disks centered at the vertices of the (regular) convex hull of the input points. Furthermore, the length of this polygon, defined over the Cartesian product of these disks, is shown to be a convex function, thus the minimum is unique and it can be computed by convex optimization.

Our problem is also related to the problem of computing bounded-curvature shortest paths in the presence of polygonal obstacles. Jacobs and Canny [START_REF] Jacobs | Planning smooth paths for mobile robots[END_REF] proved the existence of a shortest path when there exists a feasible one. 2 They also proved, in parallel with Fortune and Wilfong [START_REF] Fortune | Planning constrained motion[END_REF], that such a shortest path consists of a concatenation of Dubins paths joined at points on the boundary of the obstacles. Fortune and Wilfong [START_REF] Fortune | Planning constrained motion[END_REF] also presented an exponential-time and space algorithm for deciding the existence of a feasible path between two configurations. A few years later, Reif and Wang [START_REF] Reif | The complexity of the two dimensional curvature-constrained shortest-path problem[END_REF] showed that the decision problem corresponding to finding a shortest path is NP-hard. Several approximation algorithms were proposed [START_REF] Jacobs | Planning smooth paths for mobile robots[END_REF][START_REF] Sellen | Approximation and decision algorithms for curvature-constrained path planning: a state-space approach[END_REF][START_REF] Wang | Approximation algorithms for curvature-constrained shortest paths[END_REF]; in particular, Wang and Agarwal [START_REF] Wang | Approximation algorithms for curvature-constrained shortest paths[END_REF] presented a O( n 2 ε 2 log n)-time algorithm for computing a (1 + ε)-approximation of a shortest ε-robust path (informally, a path is ε-robust if it remains feasible after an ε-perturbation of the configurations touching the obstacles). The first polynomial-time algorithm that computes a (1 + ε)-approximation of a shortest path, or reports that there is no path shorter than a given constant ℓ, was presented by Backer and Kirkpatrick [START_REF] Backer | A complete approximation algorithm for shortest bounded-curvature paths[END_REF]; its running time is polynomial in terms of the total bit complexity of the coordinates of the polygon vertices, ε -1 , and ℓ. Shortest or feasible bounded-curvature paths have also been studied inside convex polygons [START_REF] Agarwal | Curvature-constrained shortest paths in a convex polygon[END_REF], narrow corridors [START_REF] Bereg | Curvature-bounded traversals of narrow corridors[END_REF], and among obstacles of bounded curvature [START_REF] Agarwal | Motion planning for a steering-constrained robot through moderate obstacles[END_REF][START_REF] Boissonnat | A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles[END_REF].

Note finally that other models of car-like robots have also been studied. In particular, the Reeds and Shepp model [START_REF] Reeds | Optimal paths for a car that goes both forwards and backwards[END_REF], in which both forward and backward motions are allowed, has been extensively studied. Note also that other, and more general, dynamic constraints have been considered, and that Dubins paths have been generalized to the three-dimensional case [START_REF] Sussmann | Shortest 3-dimentional paths with a prescribed curvature bound[END_REF]. We refer to [START_REF] Lavalle | Planning Algorithms[END_REF] for a recent overview of such path planning problems.

Proof outline and paper organization. The robot configuration is specified by both its location, a point p in R 2 (typically, the midpoint of the rear axle), and its direction of travel which we represent by its polar angle θ in S 1 . We consider the function F : (S 1 ) n → R that maps a sequence (θ 1 , . . . , θ n ) of angles to the length of a shortest curvature-constrained path visiting the configurations (p 1 , θ 1 ), . . . , (p n , θ n ) in order. Dubins' characterization implies that a curvature-constrained shortest path between two configurations can be computed in constant time, so computing a curvature-constrained shortest path visiting the points in order is computationally equivalent to minimizing the function F . Throughout this paper, we assume that consecutive waypoints are distance at least 4 apart, which ensures, in particular, that shortest Dubins paths have type CSC between waypoints.

In § 3, we establish that the function F is both twice differentiable and locally strictly convex at any point (θ 1 , . . . , θ n ) of a domain L(π) such that, in the shortest path visiting the configurations (p 1 , θ 1 ), . . . , (p n , θ n ), all circular arcs between consecutive waypoints have length less than π (Proposition 3.3). We start by considering the case of two points, a situation we handle by using analytical arguments and a new sufficient condition for the optimality of Dubins paths of a given type (Lemma 3.1). The local convexity for multiple waypoints easily follows from the case of two points.

In § 4, we analyze the geometry of locally shortest paths (Lemma 4.1) to show that a globally shortest path never has arcs of length greater than 3π 4 between waypoints (Proposition 4.2). To keep the presentation simple we give a proof under the assumption that consecutive waypoints are distance at least 2 + 2 √ 2 apart and outline in § 6 how this condition can be relaxed to distance 4. It follows that F is locally convex on an open domain L( 3π 4 ) containing all its global minima. The connected components of this domain are, however, not convex, and they may thus contain several local minima.

To overcome this issue, we construct, in § 5, a "nice" region D contained in the domain L(π) of local convexity of F , and containing the domain L( 3π 4 ) and thus all the global minima of F (Corollary 5.2). The connected components of D are, once lifted to R n , convex polyhedra defined by 4n inequalities each (Lemma 5.3). Again, to keep the presentation simple we first construct D assuming that consecutive waypoints are distance at least 8.6 apart and outline in § 6 how to relax that distance condition. Hence, once lifted to R n , F is convex over every connected component of D and thus its global minimum can be found by convex minimization over each of these components (Proposition 5.4). Unfortunately, there might still be Θ(2 n ) such components.

In § 7, we show that the number of components to be considered is at most exponential in the number of sharp turns (suitably defined) on the polygonal path p 1 . . . p n (Theorem 7.2). Specifically, we argue that, unless the polygonal path turns sharply at p i , the polar angle at p i of any globally shortest path must lie in a restricted range as otherwise the part of the path between p i-1 and p i+1 would have a self-intersection and therefore admit a global shortcut (Lemma 7.1).

Notation and preliminaries.

Let p 1 , . . . , p n be a sequence of points in the plane. A configuration is defined as a pair (p, θ) ∈ R 2 × S 1 where S 1 = R/2πZ denotes the space of angles. In some cases, it will be more convenient to consider angles in R, that is to lift S 1 to some interval of length 2π in R. In particular, when we discuss the local convexity of functions taking angles as input, we implicitly assume that these angles are seen in R, that is the local convexity of a function φ : (S 1 ) n → R refers to the local convexity of φ • τ , where τ is the quotient map from R n to (S 1 ) n .

We say that a sequence of points p 1 , . . . , p n satisfies the (D d ) condition if every two consecutive points p i and p i+1 are at least distance d apart. Throughout the paper we will consider that at least the (D 4 ) condition holds so that, in particular, a shortest Dubins path between any two configurations (p i , θ i ) and (p i+1 , θ i+1 ) is of type CSC [10, §4.3]3 ; furthermore, it is straightforward to bound the length of its line segment as follows.

Lemma 2.1. If p i and p i+1 are at distance d 4, then the shortest Dubins path between any configurations (p i , θ i ) and (p i+1 , θ i+1 ) has type CSC and the line segment has length at least (d -2) 2 -4.

We sometimes need to specify whether a Dubins path is turning right (clockwise) or left (counterclockwise) on a circle; we then refer to paths of types LSR, RSL, LSL, and RSR. Note that there is always a unique path of type, say LSR, between two configurations, because the circular arcs are considered to be shorter than 2π. We may also specify the length of an arc as an index; for instance, a path of type L π SR refer to a path that consists of a circular arc of length π turning left, a line segment, and a circular arc turning right.

Local convexity of the length function.

In this section we show that the problem can be recast as the minimization of a function from R n to R that is C 2 and locally convex over a certain subset of R n .

The parameterization. Let F : (S 1 ) n → R map a sequence (θ 1 , . . . , θ n ) of angles to the length of a shortest curvature-constrained path visiting the configurations (p 1 , θ 1 ), . . . , (p n , θ n ) in order. Since S 1 can be lifted to (that is, represented by) some interval of length 2π in R, we can also see F as a function from (a subset of) R n to R. Dubins' characterization implies that a curvature-constrained shortest path between two configurations can be computed in constant time. Computing a curvature-constrained shortest path visiting the points in order is thus equivalent, from a computational point of view, to finding a minimum of the function F .

The function F breaks down into

F (θ 1 , . . . , θ n ) = F 2 1 (θ 1 , θ 2 ) + . . . + F n n-1 (θ n-1 , θ n ),
where

F i+1 i (θ i , θ i+1
) is the length of the shortest path from p i to p i+1 and whose tangents in those points have polar angles θ i and θ i+1 , respectively. All functions F i+1 i behave similarly so we first focus on F 2 1 and define, for any given path type T ∈ {LSR, RSL, LSL, RSR}, the function F T (θ 1 , θ 2 ) that denotes the length of the path of type T (T -path) from (p 1 , θ 1 ) to (p 2 , θ 2 ). Each function F T is twice differentiable at any point (θ 1 , θ 2 ) such that the corresponding T -path exists and none of its arcs vanishes. The partial derivatives and Hessian of F T at such a point are

p 1 θ 1 O 1 p 2 θ 2 O 2 s α 1 α 2 ∂F T (θ 1 , θ 2 ) ∂θ i = µ i=1 µ Ci=R (1 -cos α i ) (3.1) ∂ 2 F T ∂θ i ∂θ j = δ i,j sin α i + sin α i sin α j s (3.2) det H(F T ) = sin α 1 sin α 2 1 + sin α 1 + sin α 2 s (3.3)
where α i denotes the length of the i-th circular arc of the CSC-path from p 1 to p 2 , s stands for the length of the line segment, µ B equals 1 if B is true and -1 otherwise, and δ i,j equals 1 if i = j and 0 otherwise. These proofs are nontrivial, long and technical although they use only elementary calculus and geometry.

As they shed no insight on the problem, we omit them here and refer the interested reader to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Proposition 3]. The navigation between the functions F T and F 2 1 is made possible by the next lemma.

Lemma 3.1. If both circular arcs of a CSC-path from (p 1 , θ 1 ) to (p 2 , θ 2 ) are strictly shorter than π, then all the other distinct CSC-paths are strictly longer.

Proof. We consider two geometrically distinct paths of type T and T ′ in {LSR, RSL, LSL, RSR}, from (p 1 , θ 1 ) to (p 2 , θ 2 ), such that both circular arcs of the T -path are shorter than π. We consider all possible types of T and T ′ in turn and we show using geometric arguments that, in every case, the line segment of the T -path is shorter than the one of the T ′ -path, and that the same holds for the total length of the circular arcs. Again, since these proofs are not particularly illuminating, we refer the interested reader to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Proposition 5].

Local convexity of F i+1 i . Assume that condition (D 4 ) holds. For α ∈ (0, π] we let L i+1 i (α) denote the set of angles (θ i , θ i+1 ) in (S 1 ) 2 such that both circular arcs of the shortest path from (p i , θ i ) to (p i+1 , θ i+1 ) have length (strictly) less than α. This set is well-defined because Lemma 2.1 ensures that the shortest path is of type CSC and Lemma 3.1 guarantees it is unique (since α π). Note that L i+1 i (α) is an open set, since the circular arcs must be strictly shorter than α. We call L i+1 i (α) a lemon region due to its evocative shape (see Figure 3.1).

Lemma 3.2. If the (D 4 ) condition holds, the length function F i+1 i is C 2 and locally strictly convex over L i+1 i (π). Proof. Without loss of generality it suffices to consider F 2 1 . As mentioned above, the (D 4 ) condition and the fact that (θ 1 , θ 2 ) ∈ L 2 1 (π) ensure that there is a geometrically unique shortest path from (p 1 , θ 1 ) to (p 2 , θ 2 ) and it is of type CSC. Let α 1 and α 2 denote the lengths of its circular arcs.

First, assume that neither α 1 nor α 2 vanishes. Then the type T ∈ {LSR, RSL, LSL, RSR} of the shortest path is uniquely defined. Moreover, the length of a circular arc of the T -path from (p 1 , θ 1 ) to (p 2 , θ 2 ) varies continuously in (θ 1 , θ 2 ) provided it remains in (0, 2π). Thus, in a neighborhood of (θ 1 , θ 2 ) the lengths of the circular arcs of the T -path remain in (0, π) and by Lemma 3.1 F 2 1 and F T coincide locally. Finally, since α 1 , α 2 ∈ (0, π), Equations (3.1) and (3.3)

yield that ∂ 2 F T ∂θ 2 1
and the determinant of the Hessian of F T are positive. This implies that F T is positive definite (by Sylvester's criterion) and thus F T and F 2 1 are locally strictly convex at (θ 1 , θ 2 ).

If at least one α i vanishes, at least two T and T ′ -paths coincide (T = T ′ in {LSR, . . .}), and the expressions of the derivatives of F T yield, by continuity, that F 2 1 is locally C 2 and thus locally convex at this point. We prove the strict local convexity at such a point by showing, using Taylor expansions of F T , that the graph of the function is locally strictly above its tangent plane. Specifically, if only α 1 vanishes then the Taylor expansion at order 2 suffices, except for θ 2 = 0 in which case the expansion of order 3 yields the result. The case where only α 2 vanishes is symmetric. The situation where both α 1 and α 2 vanish occur for exactly one point of L 2 1 (π), so the strict local convexity follows by continuity from the other cases. These computations are straightforward though tedious and we refer to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Theorem 6] for more details.

Local convexity of F . We still assume that condition (D 4 ) holds and we now define the n-dimensional lemon region L(α) ⊂ (S 1 ) n as the set of tuples (θ 1 , . . . , θ n ) such that the shortest path visiting the configurations (p 1 , θ 1 ), . . . , (p n , θ n ) has all its circular arcs, between any two consecutive points p i and p i+1 , of length less than α. The shortest path through a sequence of configurations (p 1 , θ 1 ), . . . , (p n , θ n ) is the concatenation of the shortest paths from (p i , θ i ) to (p i+1 , θ i+1 ) for i = 1, . . . , n -1. This ensures, with Lemmas 2.1 and 3.1, that L(α) is well-defined for any α ∈ (0, π]. This also implies that a point (θ 1 , . . . , θ n ) is in L(α) if and only if, for i = 1, . . . , n -1, the shortest path from (p i , θ i ) to (p i+1 , θ i+1 ) uses circular arcs of length less than α, that is (θ i , θ i+1 ) ∈ L i+1 i (α). This rewrites as

L(α) = n-1 i=1 (S 1 ) i-1 × L i+1 i (α) × (S 1 ) n-i-1 , (3.4)
with the convention that (S 1 ) 0 × A = A × (S 1 ) 0 = A. Proposition 3.3. If the (D 4 ) condition holds, the length function F (θ 1 , . . . , θ n ) is C 2 and locally strictly convex over L(π).

Proof. By Lemma 3.2, the function

F = n-1 i=1 F i+1 i (θ i , θ i+1 ) is C 2 over L(π).
Since a sum of locally convex functions is locally convex, F is locally convex over L(π). The functions F i+1 i are not, however, strictly convex as functions of (θ 1 , . . . , θ n ). To prove the strict local convexity of F , we consider its Hessian, well defined over L(π):

H =              ∂ 2 F 2 1 ∂θ 2 1 ∂ 2 F 2 1 ∂θ1∂θ2 0 • • • 0 ∂ 2 F 2 1 ∂θ1∂θ2 ∂ 2 F 2 1 ∂θ 2 2 + ∂ 2 F 3 2 ∂θ 2 2 ∂ 2 F 3 2 ∂θ2∂θ3 0 • • • 0 0 ∂ 2 F 3 2 ∂θ2∂θ3 ∂ 2 F 3 2 ∂θ 2 3 + ∂ 2 F 4 3 ∂θ 2 3 ∂ 2 F 4 3 ∂θ3∂θ4 0 • • • 0 0 0 ∂ 2 F 4 3 ∂θ3∂θ4 ∂ 2 F 4 3 ∂θ 2 4 + ∂ 2 F 5 4 ∂θ 2 4 ∂ 2 F 5 4 ∂θ4∂θ5 0 • • • 0 . . . . . . 0 • • • • • • 0 ∂ 2 F n n-1 ∂θn-1∂θn ∂ 2 F n n-1 ∂θ 2 n             
.

For any Θ = (θ 1 , . . . , θ n ),

Θ T HΘ = θ 1 θ 2 T   ∂ 2 F 2 1 ∂θ 2 1 ∂ 2 F 2 1 ∂θ1∂θ2 ∂ 2 F 2 1 ∂θ1∂θ2 ∂ 2 F 2 1 ∂θ 2 2   θ 1 θ 2 + θ 2 θ 3 T   ∂ 2 F 3 2 ∂θ 2 2 ∂ 2 F 3 2 ∂θ2∂θ3 ∂ 2 F 3 2 ∂θ2∂θ3 ∂ 2 F 3 2 ∂θ 2 3   θ 2 θ 3 + • • • + θ n-1 θ n T   ∂ 2 F n n-1 ∂θ 2 n-1 ∂ 2 F n n-1 ∂θn-1∂θn ∂ 2 F n n-1 ∂θn-1∂θn ∂ 2 F n n-1 ∂θ 2 n   θ n-1 θ n .
For any Θ in L(π), (θ i , θ i+1 ) belongs to the lemon L i+1 i (π), for all i = 1, . . . , n -1. Lemma 3.2 implies that every term of the above sum is strictly positive, hence H is positive definite over L(π).

4. The domain of local convexity contains all global minima. We now prove that the domain over which we know the length function to be locally convex contains all its global minima. Let γ be a shortest bounded-curvature path through a sequence of configurations (p 1 , θ 1 ), . . . , (p n , θ n ). We assume that the (D 4 ) condition holds so that γ is of type CSC between any two consecutive configurations (by Lemma 2.1). We say that the path γ is locally shortest if it cannot be shortened by small deformations (while going through p 1 , . . . , p n and remaining of bounded curvature), that is if (θ 1 , . . . , θ n ) is a local minimum of F .

Lemma 4.1. If γ is a locally shortest path, then (i) its initial and final circular arcs vanish, (ii) the two circular arcs preceding and following every point p i , 1 < i < n, have the same orientation (R or L), and (iii) their lengths are either equal or sum up to 2π. 4Proof. Since F is the minimum of several length functions, each associated with a different path type (e.g. LSR -RSR -LSR...), it is difficult to determine where F is differentiable; we only know that F is differentiable over L(π), by Lemma 3.2. We thus consider, in the proof, the length function associated with the path type of γ, instead of F . For clarity, we assume that γ visits the configurations (p i , θi ), that is we distinguish between the variables θ i and the value ( θ1 , . . . , θn ) of a local minimum of F .

Recall that the length of a CSC-path of type T from (p 1 , θ 1 ) to (p 2 , θ 2 ) is differentiable at any (θ 1 , θ 2 ) such that the circular arcs of the corresponding T -path do not vanish, and for i = 1, 2 Equation (3.1) states:

∂F T (θ 1 , θ 2 ) ∂θ i = µ i=1 µ Ci=R (1 -cos α i ).
This first implies Statement (i). Indeed, consider the subpath of γ between p 1 and p 2 , let T be its type, and suppose for a contradiction that the circular arc at p 1 does not vanish. If the circular arc at p 2 does not vanish either, then F T is differentiable at θ1 and its derivative, µ C1=R (1 -cos α 1 ), is nonzero; thus γ is not locally shortest, a contradiction. On the other hand, if the circular arc at p 2 vanishes, the type T is not uniquely defined, but it can be chosen so that the path changes continuously if θ 1 increases from θ1 (and, similarly, if θ 1 decreases); the length of the path thus changes continuously and may decrease since the derivative defined by continuity at θ1 is nonzero and does not depend on the orientation L or R at p 2 . Hence, the initial arc of γ vanishes, and similarly for its final arc.

We now prove the rest of the lemma. Consider any nonterminal point p i , and the subpath of γ between p i-1 and p i+1 ; denote γ i this subpath. Let F T (θ i ) be the length of the path from (p i-1 , θi-1 ), through (p i , θ i ), and to (p i+1 , θi+1 ), whose type before and after p i is that of γ i (these types are not uniquely defined if some circular arc vanishes). If the circular arcs of the subpath of γ do not vanish, then F T (θ i ) is differentiable at θi , and

F ′ T ( θi ) = -µ C - i =R (1 -cos α - i ) + µ C + i =R (1 -cos α + i ),
where C - i and C + i denote the circular arcs preceding and following p i , respectively, and α - i and α + i denote their lengths.

Since θi is a local minimum of F T , either F ′ T ( θi ) = 0 or F T is not differentiable at θi . In the latter case, some circular arcs of γ i vanishes, and the types of the CSC-path before and after p i can then be chosen so that the corresponding path from (p i-1 , θi-1 ), through (p i , θ i ), and to (p i+1 , θi+1 ) changes continuously, and so its length, when θ i increases from θi (and, similarly, if θ i decreases). Furthermore, the value of the derivative of F T defined by continuity at θi is independent of that choice of type (since µ C ± i =R (1-cos α ± i ) = 0 when C ± i vanishes). Hence, if the derivative is negative, the length of the path decreases when θ i increases from θi , contradicting its optimality (and, similarly, if the derivative is positive). Therefore, F ′ T ( θi ) = 0 in all cases. Now, if the orientations (R or L) of the two circular arcs C - i and

C + i differ, F ′ T ( θi ) = µ C + i =R (2 - cos α - i -cos α + i ) which is zero only if α + i = α - i = 0
; in that case, the arcs may be considered to have the same orientation, which implies Statement (ii). It follows that ) implies that the line segments preceding and following p i have length at least 2. In both cases, the path can be trivially shortened, as illustrated in 5. Reduction to a family of convex optimization sub-problems. With Propositions 3.3 and 4.2, one could hope to use convex optimization methods to find the minimum of the length function F . It is, however, clear from the example of Figure 3.1(a) that even for two points, L(π) may be non-convex; this means that there could be many (local) minima of F in every connected component of L(π). In this section, we describe a simple region D, which we call a diamond, such that L 3π 4 ⊂ D ⊂ L(π) and an adequate lifting (S 1 ) n → R n maps each connected component of D to a convex polyhedron, suitable for convex optimization.

F ′ T (θ i ) = µ C + i =R (cos α - i -cos α + i ), which is zero only if α - i = α + i or α - i + α + i = 2π
i p i (a) p i α ± i ∈ [ 3π 4 , π] α - i α + i p i α ± i ∈ [π, 3π 2 ] α - i α + i p i α ± i ∈ [ 3π 2 , 2π] α - i α + i (b)
Two-dimensional diamonds. Consider two consecutive points p i and p i+1 , and denote by ν i i+1 the polar angle of vector ----→ p i+1 p i . We define D i+1 i as the image of the open quadrilateral with vertices (0, 2π), ( π 4 , π 4 ), (2π, 0), and ( 7π 4 , 7π 4 ) under the translation of vector (ν i i+1 , ν i i+1 ) (see Figure 5.1). Twodimensional diamonds have the following property.

θ i+1 θ i ν i i+1 ν i i+1 ν i i+1 + π 4 ν i i+1 + π 4 ν i i+1 + 7π 4 ν i i+1 + 7π 4 ν i i+1 + 2π ν i i+1 + 2π Q Fig. 5.1: Diamond D i+1 i (solid), contained in L i+1 i (π) and containing L i+1 i 3π 4 (both dashed) for |p i p i+1 | = 8.6. Lemma 5.1. If |p i p i+1 | 8.6 then L i+1 i 3π 4 ⊂ D i+1 i ⊂ L i+1 i (π).
Proof. The proof is done in four steps. First, we show that we can assume without loss of generality that ν i i+1 = 0 and thus that L i+1 i (α) and D i+1 i can be lifted to the open square (0, 2π) 2 of R 2 without intersecting the square boundary. We thus refer to Figure 5.1 with ν i i+1 = 0. Second, we show that L i+1 i (α) and D i+1 i are symmetric with respect to the two diagonals of the square, which implies that it is enough to prove the inclusion in only one quadrant. Third, we give an analytical expression of the boundary of L i+1 i (α). Fourth, using these analytical expressions, we prove the inclusions

L i+1 i 3π 4 ⊂ D i+1 i ⊂ L i+1 i (π) in the considered quadrant.
Step 1. We can assume that p i+1 lies at the origin, because translating {p i , p i+1 } changes neither L i+1 i (α) nor D i+1 i . Now, rotating p i about p i+1 by any angle µ, increases θ i and θ i+1 by µ, that is, translates L i+1 i (α) and D i+1 i by vector (µ, µ). This does not change their relative positions. We can thus assume that p i+1 = (0, 0), p i = (d, 0), and ν i i+1 = 0. In any CSC-path from (p i , 0) to (p i+1 , θ i+1 ), for any θ i+1 ∈ S 1 , the circular arc following p i has length at least π.

The same property holds for paths from (p i , θ i ) to (p i+1 , 0), thus for any α π the lemon L i+1 i (α) does not intersect the two hyperplanes θ i = 0 and θ i+1 = 0. Furthermore, D i+1 i does not meet these hyperplanes either, by construction. It follows that we can lift L i+1 i (α) and D i+1 i from (S 1 ) 2 onto the open square (0, 2π) 2 of R 2 .

Step 2. We first prove that L i+1 i (α) is symmetric with respect to point (π, π) and to the lines y = x and y = 2π -x. The first symmetry is straightforward from the observation that shortest CSC-paths from (p i , θ i ) to (p i+1 , θ i+1 ) and from (p i , 2π -θ i ) to (p i+1 , 2π -θ i+1 ) are symmetric with respect to the x-axis. The second symmetry of L i+1 i (α) is similar though more subtle: it follows from the observation that shortest CSC-paths from (p i , θ i ) to (p i+1 , θ i+1 ) and from (p i , θ i+1 ) to (p i+1 , θ i ) can be transformed from one another by reversing path and then taking its mirror image with respect to, first, the bisecting line of p i and p i+1 and, second, the x-axis. Finally, the last symmetry of L i+1 i (α) is simply a composition of the two others. It is clear that D i+1 i exhibits the same symmetries, so it suffices to prove the inclusions in the quadrant Q = {0 x y 2π -x}.

Step 3. The proof of the analytical description of the boundary of L i+1 i (α) is quite intricate and goes in three steps, as follows. The path corresponding to (θ i , θ i+1 ) refers, for simplicity, to the (or any) shortest CSC-path from (p i , θ i ) to (p i+1 , θ i+1 ). We first show that any point on the boundary of L i+1 i (α) has the property that the longest circular arc of its corresponding path has length α. We then give an analytical description of arcs of curves that are guaranteed to contain any point with that property. Instead of trying to prove the reverse inclusions directly, we argue in the third step, that the union of the arcs forms a simple closed curve in [0, 2π] 2 ; since L i+1 i (α) has nonempty interior and exterior regions, its boundary must disconnect S 1 × S 1 and therefore cannot be a proper subset of a simple closed curve.

Step 3a. Suppose for a contradiction that there is a point (θ i , θ i+1 ) on the boundary of L i+1 i (α) such that a shortest CSC path from (p i , θ i ) to (p i+1 , θ i+1 ) has both its circular arcs strictly shorter than α π. In a neighborhood of (θ i , θ i+1 ), this CSC-path changes continuously while both its circular arcs remains strictly shorter than α π. By Lemma 3.1, these paths are shortest CSC-paths and thus, a neighborhood of (θ i , θ i+1 ) is included in L i+1 i (α), contradicting the assumption.

Step 3b. We show that if the path corresponding to (θ i , θ i+1 ) ∈ (0, 2π) 2 has type L α SL β or L α SR β , with β α, then (θ i , θ i+1 ) belongs to the curves of equations

C LαSL α : θ i+1 = θ i + α + arccos(cos α -d sin(θ i + α)) for π -α θ i π -α + arcsin 1 -cos α d , C LαSR α : θ i+1 = θ i + α -arccos(2 -cos α + d sin(θ i + α)) for π -α + arcsin 1 -cos α d θ i π -α + arcsin 2 -2 cos α d .
The key idea is to show that for paths of type . Their union τ is thus a connected curve, and that curve is simple since C LαSL α and C LαSR α are graphs of functions whose domains share only one point. The endpoints of τ are (π-α, π+α) and (t, t) with t = π-α+arcsin 2-2 cos α d , which belong to, respectively, the lines θ i+1 = 2π-θ i and θ i+1 = θ i . The slope of τ is everywhere less than -1 so τ lies in the quadrant Q; a straightforward calculation 5 actually shows that this slope is everywhere less than -7, a fact used in Step 4. Altogether, the 5 The derivative of the function of C LαSL α minus -7 is 8 +

L α SL β , θ i+1 = θ i + α +
d cos(θ i +α) √ 1-(cos(α)-d sin(θ i +α)) 2 .
Noting that the term in the square root is non-negative and that cos( . Hence, for any θ i and d 8.6, the slope of C LαSL α is less than that of θ i+1 = 2π -7θ i . The calculation is similar for C LαSR α .

θ i + α) 0 (since π θ i + α 3π 2 ),
union of C LαSL α and C LαSR α is thus a simple curve τ contained in the quadrant Q and with endpoints on the two diagonals of the square [0, 2π] 2 .

Step 3c. Any boundary point of L i+1 i (α) with corresponding path of type L α SL α or L α SR α must belong to τ . Step 2 then implies that any boundary point of L i+1 i (α) must belong to τ or one of its image under the central symmetry with respect to (π, π), the reflection with respect to the line θ i+1 = θ i , and their composition. Let σ denote the union of τ and its images under these transformations. Since τ is a simple arc of curve that lies in the quadrant Q with its endpoints on the lines θ i+1 = θ i and

θ i+1 = 2π -θ i , σ is a simple closed curve in [0, 2π] 2 .
Let σ denote the projection of σ on S 1 × S 1 . If α < π, σ lies in the open square (0, 2π) 2 and σ is thus a simple closed curve. If α = π, the two points (0, 2π) and (2π, 0) of σ are mapped to the same point of σ, and σ then consists of two simple loops meeting in exactly the point (0, 0). When α π, the boundary of L i+1 i (α) cannot be a proper subset of a simple closed curve since both that set and its complement have interior points. It follows that when α < π, the boundary of L i+1 i (α) is the whole curve σ; the same holds when α = π as, in that case, both loops forming σ contain some point of the boundary of L i+1 i (π).

Step 4. The segment that bounds D i+1 i in the quadrant Q lies on the line θ i+1 = 2π-7θ i with θ i ranging from 0 to π 4 . We have shown that the boundary of

L i+1 i (α) in Q is C LπSL π ∪ C
LπSR π which slope is less than -7 everywhere. Since the leftmost point of C LπSL π ∪ C LπSR π is (0, 2π) which lies on the line θ i+1 = 2π -7θ i , the boundary of L i+1 i (π) is strictly below that of D i+1 i , in Q, except for their endpoint (0, 2π). On the other hand, a simple calculation also shows that the rightmost point of

C L 3π 4 SL 3π 4 ∪ C L 3π 4 SR 3π 4
is strictly above the line θ i+1 = 2π -7θ i , which implies that the boundary of

L i+1 i ( 3π
4 ) is strictly above that of D i+1 i , in Q, and concludes the proof.

n-dimensional diamond D. We extend the construction of the two-dimensional diamond D i+1 i to an arbitrary number of points by defining the diamond of p 1 , . . . , p n as

D = n-1 i=1 (S 1 ) i-1 × D i+1 i × (S 1 ) n-i-1 , (5.1)
with the convention that (S 1 ) 0 × A = A × (S 1 ) 0 = A. The similarity with Equation (3.4),

L(α) = n i=1 (S 1 ) i-1 × L i+1 i (α) × (S 1 ) n-i-1 ,
and the inclusions Lifting D to convex polyhedra. Recall that ν i i+1 denotes the polar angles of ----→ p i+1 p i . For i = 1, . . . , n -1, let Λ i be the interval (closed on its left side and open on its right side) of length 2π that contains 0 and has its endpoints in ν i i+1 + 2πZ, and let

L i+1 i 3π 4 ⊂ D i+1 i ⊂ L i+1 i (π)
Λ n = Λ n-1 . Now, let Λ = 1 i n Λ i ⊂ R n .
We lift D to R n through the lifting (S 1 ) n → Λ. See Figure 5.2 for an illustration and note that, through this lifting, the image of one diamond D i+1 i (or, more formally, of (S

1 ) i-1 × D i+1 i × (S 1 ) n-i-1
) is in general not connected. For 1 < i < n, Λ i contains one point from ν i-1 i + 2πZ which splits it into two intervals; we denote the larger of these intervals by Λ + i and the smaller by Λ - i (if the two intervals have the same length the names have no importance); by convention we let Λ

+ 1 = Λ - 1 = Λ 1 and Λ + n = Λ - n = Λ n . Finally, consider the family of hyperplanes in (S 1 ) n H = {θ i = ν i i+1 | i = 1, . . . , n -1} ∪ {θ i = ν i-1 i | i = 2, . . . , n}.
Lemma 5.3. D does not intersect the hyperplanes of H, and the lifting (S 1 ) n → Λ maps the intersection of D with each cell of (S 1 ) n \ H to a convex polyhedron defined by at most 4n linear inequalities in R n , each involving 2 variables. Proof. Since D i+1 i intersects none of the lines θ i = ν i i+1 and θ i+1 = ν i i+1 , in (S 1 ) 2 , the diamond D intersects none of the hyperplanes of H.

(ν i-1 i , ν i i+1 , ν i+1 i+2 ) θ i-1 θ i+1 ν i i+1 ν i+1 i+2 + 2π Λ + i-1 Λ + i ν i i+1 + 2π θ i ν i-1 i-2 ν i-1 i + 2π D i i-1 D i i-1 D i+1 i Λ - i Λ - i-1 Λ - i+1 D i+1 i Λ + i+1 ν i-1 i
In the lifting of (S 1 ) n to Λ, each cell of (S 1 ) n \ H is lifted to a box Ξ = 1 i n Λ εi i where ε i ∈ {-, +}. By definition of D i+1 i , its pre-image under the quotient map R 2 → (S 1 ) 2 is a family of disjoint convex quadrilaterals, one in each open square defined by the lines θ i = ν i i+1 + 2πZ and θ i+1 = ν i i+1 + 2πZ, in R 2 . The interior of the rectangle Λ εi i × Λ εi+1 i+1 does not intersect those lines and therefore meets at most one of the convex quadrilaterals of the pre-image. It follows that the image of D i+1 i through the partial lift (S 1 ) 2 → Λ εi i × Λ εi+1 i+1 is a convex polygon defined by at most 8 inequalities: the 4 defining the quadrilateral and the 4 defining the boundary of the rectangle.

The image of D through the (partial) lift (S 1 ) n → Ξ is thus a convex polyhedron defined by at most 8(n -1) inequalities, in one or two variables each. However, 4(n -1) of these inequalities are sufficient: since the closure of D intersects no hyperplane of H in a face of dimension more than n -2, we can drop, for each D i+1 i , the 4 inequalities defining the boundary of Λ εi i × Λ εi+1 i+1 . Convex optimization sub-problems. We can now prove that computing a global shortest path through a sequence of points reduces to solving (possibly exponentially many) convex optimizations sub-problems.

Proposition 5.4. Let p 1 , . . . , p n be a sequence of points in the plane such that any two consecutive points are at least distance 8.6 apart. All global minima of F are realized in an open domain of (S 1 ) n that can be lifted to a union of up to 2 n-2 disjoint convex polyhedra in R n , each defined by at most 4n linear inequalities, in two variables each. Moreover, through this lifting, F is strictly convex over each of these polyhedra.

Proof. The global minimum of F is realized over D as it is realized over L 3π 4

(by Proposition 4.2) and L 3π 4 ⊂ D (by Corollary 5.2). For each cell c in (S 1 ) n \ H, the lifting (S 1 ) n → Λ maps D ∩ c to a convex polyhedron in R n defined by 4n linear inequalities (by Lemma 5.3). Moreover, the length function F is convex on each such polyhedron since it is convex on L(π) (by Proposition 3.3) and D ⊂ L(π) (by Corollary 5.2). Since (S 1 ) n \ H has at most 2 n-2 cells, the statement follows.

Note that the length function F may actually have up to 2 n-2 local minima as the example of Figure 5. ( § 6) and by narrowing down the set of sub-problems sufficient to consider ( § 7).

i p i-1 p i p i-1 p i p i-1 p i p i-1 α - i α - i p i p i+1 p i-1
6. Relaxing the distance conditions. We now review and sharpen our chain of arguments so that our reduction to convex optimization holds under the (D 4 ) condition.

All the arguments regarding the local convexity of the length function over L(π) holds under the (D 4 ) condition (in fact, the (D 4 ) condition is only used there to evacuate the need to consider CCC-paths). There is thus nothing to add to § 3.

In § 4, the fact that any global minimum of F lies in L 3π 4 (Proposition 4.2) follows from the property that, if the length of a circular arc preceding or following p i is more than 3π 4 , then the path can be globally shortened between p i-1 and p i+1 . The (D 2+2 √ 2 ) condition allowed for a simple proof of this property because the segments preceding and following p i have length at least 2. Under the (D 4 ) condition, this property can still be proven by applying adequate local transformations (illustrated in Figure 6.1). A more intricate case analysis is needed and we refer the interested reader to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Lemma 11] for more details.

In § 5, the construction of the "nice" domain D, the (D 8.6 ) condition is used in the proof of the inclusions (Lemma 5.1). It turns out that these inclusions may fail under a weaker distance condition. We address this issue by making the diamond D i+1 i sensitive

L i+1 i 3π 4 ⊂ D i+1 i ⊂ L i+1 i (π)
ν i i+1 ν i i+1 + 2π θ i θ i+1 ν i i+1 ν i i+1 + ξ i ν i i+1 + 2π -ξ i ν i i+1 + 2π
to the distance between the points. Specifically, with d i = |p i p i+1 | and ξ i = 2π/(d i -1/d i ), we define D i+1 i as the image of the open quadrilateral with vertices (0, 2π) , (ξ i , ξ i ) , (2π, 0) , and (2π -ξ i , 2π -ξ i ) under the translation of vector (ν i i+1 , ν i i+1 ). The inclusions L i+1 The arguments are standard though long and non-trivial, as we compute the sign of functions at their local extrema by bounding their values using partial sums of power series and Descartes' rule of signs. We refer the interested reader to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Lemma 15] for details. The n-dimensional diamond is then defined as before (Equation (5.1)) and the extension of the inclusions from the 2 to the d dimensional setting remain unchanged.

Altogether, this improves Proposition 5.4 as follows. Theorem 6.1. Let p 1 , . . . , p n be a sequence of points in the plane such that any two consecutive points are at least distance 4 apart. All global minima of F are realized in an open domain of (S 1 ) n that can be lifted to a union of up to 2 n-2 disjoint convex polyhedra in R n , each defined by at most 4n linear inequalities, in two variables each. Moreover, through this lifting, F is strictly convex over each of these polyhedra.

7.

Reducing the number of sub-problems. Proposition 5.4 reduces the computation of a global minimum of F to the resolution of up to 2 n-2 convex optimization sub-problems. To choose a sub-problem to consider means to fix one of the cells i Λ εi i as a candidate cell for containing the global minimum of F . This choice has a simple geometric interpretation which can be used to considerably reduce the number of sub-problems to consider (Theorem 7.2).

p i p i-1 p i+1 region of negative ε i (γ)
"Class" of a shortest path. Let γ stand for the curvatureconstrained shortest path that visits the configurations (p 1 , θ 1 ) . . . , (p n , θ n ) in order. Let ε i (γ) = -if the tangent to γ at p i lies in the positive cone of the vectors ----→ p i p i-1 and ----→ p i+1 p i and + otherwise. It is clear that ε i (γ) = + if and only if θ i ∈ Λ + i .6 Thus, if we can compute the "class" (ε 1 (•), . . . , ε n (•)) of the globally shortest path visiting p 1 , . . . , p n , then computing that path reduces to a single convex optimization problem. Figure 5.3 shows two paths in distinct classes. Sharp turns. We now argue that unless the polygonal path p i-1 p i p i+1 makes a "sharp turn" at p i , the tangent to the globally shortest path visiting p 1 , . . . , p n in order must belong to the positive cone of ----→ p i p i-1 and ----→ p i+1 p i ; in other words the "class" of the globally shortest path in p i is trivial. Formally, we say that p i-1 , p i , p i+1 form a sharp turn, or for simplicity that p i is a sharp turn, if the triangle p i-1 p i p i+1 is acute at p i and if the distance from p i-1 to the segment p i p i+1 , or the distance from p i+1 to the segment p i p i-1 , is at most 4.

Lemma 7.1. Let γ be a globally shortest path visiting p 1 , . . . , p n in order and assume that the (D 4 ) condition holds. If p i is not a sharp turn then ε i (γ) = +.

Proof. Let γ be a globally shortest path. Assume, for a contradiction, that the polar angle θ i of its tangent vector at p i is in Λ - i , and that p i is not a sharp turn. We show that the arc of γ from p i-1 to p i+1 has a self-intersection which allows a global shortening of γ, contradicting the assumption that this path is globally shortest. To keep the notations simple we consider without loss of generality that i = 2.

Existence of a self-intersection. Refer to Figure 7.1(a). Let ℓ be the oriented line tangent to the (oriented) path γ at p 2 , and, for any two distinct points a and b, let (ab) denote the oriented line from a to b. Without loss of generality, we assume that p 1 is to the left7 of ℓ; since θ 2 ∈ Λ - 2 , p 3 is to the left of ℓ and to the right of (p 1 p 2 ). Moreover, if p 3 is on (p 1 p 2 ) then p 2 is a sharp turn, so p 3 is strictly to the right of (p 1 p 2 ) and, similarly, p 1 is strictly to the left of (p 3 p 2 ).

ℓ p 1 p 2 p 3 m 1 m 3 --→ p 2 p 1 --→ p 3 p 2 (a) p 2 C 3 C 4 C 1 C 2 T + 1 T + 2 T + 3 T + 4 T - 1 T - 3 T - 2 T - 4 I Q L - L + (b) Fig. 7.1: (a) If θ 2 ∈ Λ -
2 and p 2 is not a sharp turn, the path self-intersects. (For clarity the vectors are not drawn to scale.) (b) Shortening a path that self-intersects.

For j = 1, 3 let γ j denote the portion of γ between p j and p 2 . By Proposition 4.2 (or, rather, its generalization under the (D 4 ) condition mentioned in § 6), the circular arcs of γ j have length at most 3π 4 , which is strictly less than π. Thus, p 1 and p 3 are strictly to the left of ℓ, and γ 1 and γ 3 are also entirely strictly to the left of ℓ, except for p 2 .

We now argue that γ 1 intersects the line (p 2 p 3 ) in p 2 and exactly one other point, denoted m 1 , at which γ 1 traverses (p 2 p 3 ). Let c be the number of intersection points between γ 1 \ p 2 and (p 3 p 2 ), counted with multiplicity. We first observe that γ crosses the line (p 3 p 2 ) from right to left in p 2 , and p 1 is strictly to the left of (p 3 p 2 ), so c must be odd. Next, γ 1 intersects any line other than the line supporting "its" segment, in at most three points, counted with multiplicity. Indeed, since the circular arcs have length at most π, if a circular arc meets the line in two points (possibly identical), then the segment does not intersect the line in another point, and the second circular arc intersects the line in at most one point (counted with multiplicity). Since p 2 contributes at least one to this count, c must be at most two. Since c must also be odd, c = 1 and γ 1 intersects (p 2 p 3 ) in p 2 and exactly one other point m 1 , at which it traverses this line.

We furthermore prove that m 1 belongs to the open segment [p 2 p 3 ]. First, since γ 1 is to the left of ℓ, so is m 1 . As p 2 is on ℓ and p 3 is strictly to the left of ℓ, it follows that either m 1 belongs to the segment [p 2 p 3 ], or p 3 belongs to the segment [p 2 m 1 ]. In the latter case, p 3 lies in the convex hull of γ 1 and is thus within distance at most 2 from the segment of γ 1 ; this is impossible, as it would imply that p 3 is at distance at most 4 from the segment p 1 p 2 , i.e. that p 2 is a sharp turn. Hence Consider now the curve ρ obtained as the union of γ 1 and the segment [p 1 p 2 ]. It is closed, and thus delimits a bounded region R (shown in gray in Figure 7.1(a)). Note that the line (p 2 p 3 ) meets ρ in exactly {m 1 , p 2 }, and m 1 lies strictly in-between p 2 and p 3 , thus p 3 lies strictly outside the region R.

Consider finally the intersection between γ 3 and ρ. Let γ ′ j be γ j minus its endpoint p 2 . γ ′ 3 intersects the line (p 1 p 2 ) in exactly one point, m 3 , at which it traverses (p 1 p 2 ). Since m 3 lies on the open segment [p 1 p 2 ], either m 3 is a (the) point of self-intersection of ρ, or γ ′ 3 intersects the interior of R in a neighborhood of m 3 . In the former case, m 3 then lies on γ ′ 1 and thus γ is self-intersecting between p 1 and p 3 . In the latter case, when γ ′ 3 intersects the interior of R, γ ′ 3 must intersect ρ in some other point because γ ′ 3 does not intersect R in some neighborhoods of p 2 and p 3 . Since γ 3 is simple and intersects line (p 2 p 3 ) only at p 2 and m 3 , γ ′ 3 must intersect γ ′ 1 . Then, again, γ is self-intersecting between p 1 and p 3 .

Fixed initial and final directions. If the initial and/or the final directions of the path are fixed, a globally shortest path may have a circular arc of length more than π incident to p 1 or p n . This invalidates our sufficient condition for a CSC-path to be the shortest Dubins path between two configurations (Lemma 3.1) which was crucial for establishing the local convexity of F . A way around this difficulty is to consider four fixed-type length functions where the orientations (L or R) of the circular arcs following p 1 and preceding p n are imposed. Our previous proof structure yields, mutatis mutandis, that each fixed-type length function is locally strictly convex at any point (θ 2 , . . . , θ n-1 ) such that every circular arc preceding or following a waypoint has length less than π, except the initial and/or final ones. From there, the rest of the proof can be easily adapted to show that the fixed-type length functions realize their global minima over some number of polyhedra over which they are locally strictly convex. The minimum of all fixed-type functions over all these polyhedra yields the minimum of the original length function F . See the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Section 9.1] for a more detailed discussion.

Obstacles. Our technique opens the way to a new approach to path planning among polygonal obstacles. It is known that a bounded-curvature shortest path between two configurations in the presence of polygonal obstacles is a concatenation of Dubins paths whose extremities are extremal configurations or contact points on the boundary of the obstacles [START_REF] Fortune | Planning constrained motion[END_REF][START_REF] Jacobs | Planning smooth paths for mobile robots[END_REF]. It can be shown that, given the sequence of contact points and knowing which one lie on anchored circular arcs (i.e., arcs of the path that touch the obstacle more than once), the reconstruction of the whole path reduces, under certain conditions, to a family of convex optimization problems; in other words, comparatively, "connecting the dots" is now relatively easy, and the difficult task appears to be the discrete sub-problem of computing the contact points and the anchored circular arcs. A candidate setting in which this question could perhaps be tackled is inside a simple polygon, where the homotopy class of the shortest path is trivial. We, again, refer the interested reader to the technical report [15, Section 9.2] for details.

Distance condition. The requirement that the points p 1 , . . . , p n satisfy the (D 4 ) condition is used in three places. First, it excludes the occurrence of CCC-paths. Then, it is used to argue that the global minima of the length function F belong to the lemon L( 3π 4 ) (Proposition 4.2). Finally, it is instrumental for proving that the minima of F can be searched for in convex components over which F is convex (Lemma 5.1). Further relaxing the distance condition in these theorems therefore seems a considerable task. In particular, this would require to study the convexity properties of the length function of CCC paths, a task we did not undertake.

An alternative approach?. Lemma 4.1 and Proposition 4.2 imply that, under the (D 4 ) condition, if there is a globally shortest path starting from p 1 with a given direction -→ u and visiting p 1 , . . . , p n in order, that path is unique and can easily be computed. Indeed, there is at most one p 1 u p 2 circular arc of length less than 3π 4 that is tangent to the ray p 1 + R -→ u and ends in p 2 ; the circular arc leaving p 2 must have the same length and orientation (the case where both arcs sum to 2π in Lemma 4.1 being ruled out by Proposition 4.2) so the ray supporting the segment following p 2 is fixed. An immediate induction determines the path upto the ray following p n-1 and this ray must contain p n for the path to be globally shortest. Of course, if at some point, the ray following p i is too far away from p i+1 then the path cannot be continued and -→ u is not the initial direction of a globally shortest path. The problem then reduces to finding a zero of the signed distance from the final ray to p n , seen as a function of the polar angle θ 1 of -→ u .It seems plausible that this function is well-behaved (e.g. piecewise monotonic in θ 1 ) and that simple methods such as binary search could perhaps be used. However, this function can have at least 2 n-2 zeros, as shown by the lower-bound example depicted in Figure 5.3, so this approach is likely to face the same combinatorial explosion as our reduction to convex optimization.

Fig. 3 .

 3 Fig. 3.1: (a) Lemon L 2 1 (π) for |p 1 p 2 | = 4 (where ν is the polar angle of --→ p 2 p 1 ) and (b) graph of F 2 1 over that domain.

  Figures 4.1(a) and 4.1(b), by using new circular arcs and a new direction of travel at p i (shown in dashed in the figure). This contradicts the global optimality of γ.

  p

Fig. 4 . 1 :

 41 Fig. 4.1: Global shortcuts (in dashed) of locally shortest paths, for the proof of Proposition 4.2.

  β and cos β = cos α -d sin(θ i + α); plugging the latter equation into the former, while carefully monitoring modulo effects, yields the equation of C LαSL α (see [15, Section B2] for details). Paths of type L α SR α are handled similarly and lead to the equation of C LαSR α . The curves C LαSL α and C LαSR α meet in one of their endpoints, at θ i = π -α + arcsin 1-cos α d and θ i+1 = π + arcsin 1-cos α d

  from Lemma 5.1 yield: Corollary 5.2. If p 1 , . . . , p n satisfy the (D 8.6 ) condition then L 3π 4 ⊂ D ⊂ L(π).

Fig. 5 . 2 :

 52 Fig. 5.2: Illustration of the images of D i i-1 and D i+1 i through the lifting (S 1 ) n → Λ. The hyperplanes of H that are not on the boundary of Λ (through the lifting) are shown in dashed.

5 2dFig. 5 . 3 :

 553 Fig. 5.3: A sequence of n points {(2i, (-1) i d) | i = 1, . . . , n} such that, for d large enough, the sequences of polar angles (θ 2 , . . . , θ n-1 ) in {0, π} n-2 define 2 n-2 paths that are arbitrarily close to distinct local optima (two of which are shown).

  p

Fig. 6 . 1 :

 61 Fig. 6.1: (Left and center) The two elementary transformations used to prove Proposition 4.2 under the (D 4 ) condition. (Right) A combination of the two transformations that shortens the path through p i .

  under the (D 4 ) condition, for the new D i+1 i , are then proved in a similar way as in Lemma 5.1: we compare the analytical expressions of the boundaries of L i+1 i (α) and D i+1 i (in a single quadrant of the domain since the symmetries of L i+1 i (α) and D i+1 i remain unchanged).

  m 1 belongs to the closed segment [p 2 p 3 ]. Finally, m 1 = p 2 by definition, and m 1 = p 3 because otherwise p 3 lies in the convex hull of γ 1 , again requiring that p 2 be a sharp turn. Similarly, γ 3 intersects (p 1 p 2 ) in p 2 and exactly one other point, denoted m 3 which belongs to the open segment [p 1 p 2 ].

  modulo 2π; moreover these equalities are true not modulo 2π since 0 α ± i < 2π, which proves Statement (iii). We now prove that all the global minima of the length function F belong not only to L(π), but to the smaller lemon L 3π 4 . This sharper result will be useful later. Proposition 4.2. Under condition (D 2+2 √ 2 ), in any globally shortest path γ the circular arcs preceding and following each waypoint have length less than 3π 4 . Proof. As before, let C - i and C + i denote the circular arcs of γ that precede and follow p i , respectively, and α -

i and α + i be their lengths. By Lemma 4.1, since γ is a locally shortest path, α - i and α + i are equal or sum up to 2π. By Lemma 2.1, (D 2+2 √ 2

Indeed, if p i and p i+1 are at least distance d apart, with d 4, they are connected by a path of type CS whose length is at most d +

2π -2 arctan d. This method thus builds a path of length at most n -1 times this value, whereas any path has length at least (n -1) d. For d = 4, the ratio gives a bound of 1.91.2 Note that this is not trivial and actually not true when reversals are allowed[START_REF] Desaulniers | On shortest paths for a car-like robot maneuvering around obstacles[END_REF], that is for the model of Reeds and Shepp[START_REF] Reeds | Optimal paths for a car that goes both forwards and backwards[END_REF].

Although they do not state it explicitly, Bui et al.[START_REF] Bui | The shortest paths synthesis for non-holonomic robots moving forwards[END_REF] show that if a shortest Dubins path is of type CCC between ps and p f , then p f lies inside a disk of radius 2 (denoted C H ) which contains ps. Furthermore, if p f lies on the boundary of that disk, then the path is also of type CSC with the line segment of length zero.

A near reciprocal of this statement actually holds; see[START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF] Proposition 9].

If ----→ p i p i-1 and ----→ p i+1 p i are opposite then ε i (γ) is defined so as to be consistent with the definition of Λ ± i .

Unless specified otherwise, the constraint to be to the left (or to the right) of an oriented line is considered non-strict.

The complexity is considered in an extended real RAM model where arithmetic operations, trigonometric and inverse trigonometric functions, and the min function can be evaluated in constant time over the reals.

Acknowledgment. The authors would like to thank Jean-Daniel Boissonnat for his implication at a very early stage of this work, during the PhD of the third author, Otfried Cheong for helpful discussions and the two anonymous referees for their many valuable suggestions and in particular the second referee for pointing out the alternative approach sketched in the last section.

* This work was supported by the INRIA Équipe Associée KI and, in part, by Mid-career Researcher Program through NRF grant (No. R01-2008-000-11607-0) funded by the MEST and, in part, by SRC-GAIA through NRF grant (No. 2011-0030044) funded by the Government of Korea.

The self-intersection is between the two line segments. Let C - i and C + i denote the circular arcs of γ that precede and follow p i , respectively, and S -and S + the line segments that precede and follow p 2 . The self-intersection identified above is an intersection between two elements in {C + 1 , S -, C - 2 , C + 2 , S + , C - 3 }. We discuss the various situations in turn. We assume here that the distance |p i p i+1 | > 4; by continuity, the result will still hold under the non-strict (D 4 ) condition. Note also that |p 1 p 3 | > 4 since p 2 is not a sharp turn.

The self-intersection cannot be between two circular arcs. Indeed, if i = j, C ± i and C ± j cannot intersect since |p i p j | > 4. Furthermore, since γ is locally shortest, Proposition 4.2 (and § 6) ensures that C - 2 and C + 2 have length at most 3π 4 and they cannot intersect (other than at p 2 ). The self-intersection cannot be between a circular arc and a segment either. Any point in S + is within distance at most 2 from the segment p 2 p 3 . Since p 2 is not a sharp turn, the distance from p 1 to the segment p 2 p 3 is more than 4 so C + 1 cannot intersect S + . Similarly, C - 3 and S -do not intersect. Since both S + and S -are tangent to the circle supporting C - 2 and C + 2 and to, respectively, C - 3 and C + 1 , no other intersection between a circular arc and a segment is possible.

We therefore know that S -and S + intersect in some point I.

Global shortening of the path. Let L -and L + denote the two lines supporting S -and S + . We consider the four unit circles C 1 , . . . , C 4 tangent to both lines, and label the line/circle contact points as shown in Figure 7.1(b). We assume that T + 1 , T + 2 , T + 3 , and T + 4 appear in this order on L + ; this is without loss of generality because the arcs C ± i are shorter than 3π 4 . Let Q denote the endpoint of S + other than T + 1 . If T + 3 / ∈ S + then Q lies between T + 3 and I, and each of the two unit circles tangent to L + at Q intersect L -. The ray starting at T - 1 and containing S -then intersects each of the disks of radius 2 centered in p 1 and p 3 . If that ray meets the disk centered in p 1 first, then p 1 is distance at most 4 from the segment p 2 p 3 , and a similar argument holds in the symmetric case. Hence, p 2 is a sharp turn, a contradiction. It must therefore be that T + 3 lies on S + . A symmetric argument shows that T - 2 lies on S -. We can thus shorten γ using arcs of C 2 and C 3 (see Figure 7.1(b)), which concludes the proof.

We can now improve Theorem 6.1 as follows. Theorem 7.2. Let p 1 , . . . , p n be a sequence of points in the plane that has k sharp turns and such that any two consecutive points are at least distance 4 apart. All global minima of F are realized in an open domain of (S 1 ) n that can be lifted to a union of up to 2 k disjoint convex polyhedra in R n , each defined by at most 4n linear inequalities, in two variables each. Moreover, through this lifting, F is strictly convex over each of these polyhedra.

Proof. Let γ be a globally shortest path visiting p 1 , . . . , p n . If p i is not a sharp turn then, the polar angle θ i of γ at p i belongs to Λ + i by Lemma 7.1. Thus all global minima of F belong to the 2 k cells of (S 1 ) n \ H defined as i Λ εi i where ε i = + if p i is not a sharp turn, and ε i = ± otherwise. The result then follows as in Proposition 5.4 and Theorem 6.1.

Extensions and perspectives. We conclude this paper by an overview of various refinements and extensions of our results.

Complexity analysis. There are essentially two general methods that solve convex optimization problems with guaranteed complexity, the ellipsoid method and the class of interior point methods. While the latter is usually more efficient, it only works if one can compute so-called self-concordant barriers for the function to be minimized and its constraints. In our problem, the function F to be minimized is defined as the sum of minima of expressions using inverse trigonometric functions, for which computing self-concordant barriers currently seems out of reach. For the ellipsoid method, the number of steps needed to achieve an additive error of at most ε on the solution depends on the fatness of the domain [4, Theorem 5.2.1], which we only managed to analyze for the sub-problem D ∩ i Λ + i under the (D 4.3 ) condition. As a consequence, under that distance condition and in the absence of sharp turn, we can compute a path (of curvature at most 1 that visits the p i in order) whose length exceeds that of an optimal path by at most an additive constant ε in time 8 O n 4 log n ε , which is the usual complexity for the ellipsoid method in dimension n. We refer to the technical report [START_REF] Goaoc | Bounded-curvature shortest paths through a sequence of points[END_REF]Section 8] for the details of the analysis.