Bruno Jartoux
email: jartoux@post.bgu.ac.il

Nabil H Mustafa
email: mustafan@esiee.fr

A Tight Analysis of Geometric Local Search

Keywords: local search, expansion, matchings, Hall's marriage theorem Mathematics Subject Classification (2010) 68W25, 90C27, 68R10

The last decade has seen the resolution of several basic NP-complete problems in geometric combinatorial optimisation-interestingly, all with the same algorithm: local search. This includes the existence of polynomial-time approximation schemes (PTASs) for hitting set, set cover, dominating set, independent set, and other problems for some basic geometric objects. More precisely, it was shown that for many of these problems, local search with radius λ gives a (1 + O(λ -1 2 ))approximation with running time n O(λ ) . Setting λ = Θ (ε -2 ) yields a PTAS with a running time of n O(ε -2 ) .

On the other hand, hardness results suggest that there do not exist PTASs for these problems with running time poly(n) • f (ε) for any arbitrary computable f . Thus the main question left open in previous work is in improving the exponent of n to o(ε -2 ).

Our main result is that the approximation guarantee of the standard local search algorithm cannot be improved for any of these problems, which we show by constructing instances with poor "locally optimal solutions". The key ingredient, of independent interest, is a new lower bound on locally expanding planar graphs. Our construction extends to other graph families with small separators.

Introduction

Within the past decade polynomial-time approximation schemes (PTASs) have been proposed for a number of long-standing open problems in geometric approximation algorithms, including the following NP-hard problems (see [START_REF] Hochbaum | Fast approximation algorithms for a nonconvex covering problem[END_REF][START_REF] Clark | Unit disk graphs[END_REF] for hardness results). A family of pseudodisks is a set of planar regions whose boundaries are Jordan curves and such that the boundaries of any pair of pseudodisks intersect at most twice.

Hitting set for pseudodisks [START_REF] Mustafa | Improved results on geometric hitting set problems[END_REF]: given a set P of points and a family D of pseudodisks in the plane, compute a smallest subset of P that intersects all pseudodisks in D. Independent set of pseudodisks [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF][START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF]: given a family D of pseudodisks in the plane, compute a maximum size subset of pairwise disjoint pseudodisks in D. Dominating set of pseudodisks [START_REF] Gibson | Algorithms for dominating set in disk graphs: Breaking the log n barrier[END_REF][START_REF] Basu Roy | Packing and covering with non-piercing regions[END_REF]: given a family D of pseudodisks in the plane, compute a smallest subset of pseudodisks of D that together intersect all other pseudodisks of D. Set cover for disks [START_REF] Chan | Exact algorithms and APX-hardness results for geometric packing and covering problems[END_REF][START_REF] Aschner | Approximation schemes for covering and packing[END_REF]: given a set P of points and a family D of disks in the plane, return a smallest subset of disks in D whose union cover all points of P. Constant-capacity point-packing: given a set P of points, a set D of disks and a positive integer k ≤ |P|, compute a largest subset of P that hits no disk of D more than k times [START_REF] Ene | Geometric packing under non-uniform constraints[END_REF][START_REF] Raman | Planar Support for Non-piercing Regions and Applications[END_REF].

Local search

Surprisingly, the PTAS for all these problems is essentially the same: local search. Let X be the set of base elements of the problem, and let the search radius λ ≥ 3 be an integer. Then start with any feasible solution S ⊆ X and increase (in the case of a maximization problem, e.g., maximum independent set) or decrease (in the case of a minimization problem, e.g., minimum hitting set) its size by local improvement steps while maintaining feasibility. Here a local improvement step is to swap a subset S of at most λ elements of the current solution S for a subset of X \ S of size at least |S | + 1 (for maximization problems) or at most |S | -1 (for minimization problems), as long as the new solution is still feasible. The algorithm finishes when no local improvement step is possible. Such a solution is called λ -locally optimal. All these algorithms are analysed in a similar way, as follows. Let S be a λlocally optimal solution and O = S be an optimal solution. We can assume that these solutions are disjoint by considering S \ O and O \ S rather than S and O: as (

The construction of exchange graphs exploits the geometric properties of locally optimal solutions and was initially problem-specific. For example, in the minimum vertex cover problem on a graph G this would simply be the bipartite subgraph of G induced by S and O; condition (1) follows from the local optimality of S . However, in a recent paper Raman and Ray show that the problems listed above are subcases of a more general problem about the intersection hypergraph of two families of pseudodisks [START_REF] Raman | Planar Support for Non-piercing Regions and Applications[END_REF]. They propose a single algorithm to build exchange graphs for all said problems.

The key in the analysis lies in a general theorem on local expansion in sparse graphs. A bipartite graph on vertex sets (B, R) is λ -expanding if for all B ⊆ B of size at most λ we have |N(B )| ≥ |B |. Note that the roles of B and R in this definition are not symmetric. A (vertex) separator of a graph on n vertices is a subset of vertices whose removal leaves connected components of cardinality at most 2 3 n. A class of graphs G has the separator property with parameter s ∈ [0, 1] if there exists a positive constant c such that any graph in G has a separator of size at most cn1-s , where n is the number of vertices. For example, trees have this property with s = 1 (constant-sized separators) whereas planar graphs have the separator property with parameter s = 1 2 . In fact, the separator property with s = 1 2 actually holds for graphs excluding fixed minors and in particular for minor-closed classes other than the class of all graphs, e.g. graphs of bounded genus [START_REF] Alon | A separator theorem for nonplanar graphs[END_REF]. A class of graphs closed under taking subgraphs is called monotone.

The following result can be pieced together from the analysis of local search by Aschner et al. [START_REF] Aschner | Approximation schemes for covering and packing[END_REF] and is also implicit in previous papers [START_REF] Mustafa | Improved results on geometric hitting set problems[END_REF][START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF] for s = 1/2.

Theorem A ( [START_REF] Mustafa | Improved results on geometric hitting set problems[END_REF][START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF][START_REF] Aschner | Approximation schemes for covering and packing[END_REF]). If a λ -expanding bipartite graph on (B, R) belongs to a monotone family with the separator property with parameter s ∈ (0, 1) and λ ≥ λ s , then |B| ≤ (1 + c s λ -s ) • |R|, where c s and λ s are positive constants that depend only on s. [START_REF] Cabello | Simple PTAS's for families of graphs excluding a minor[END_REF] describe a subcase of this theorem for K h -minor-free graphs, which have separators of size O h 3/2 √ n . Finally, Har-Peled and Quanrud [18,[START_REF] Har-Peled | Notes on approximation algorithms for polynomial-expansion and lowdensity graphs[END_REF] observe that intersection graphs of low-density objects in R d have the separator property with s = 1 d . To complete the analysis for minimization problems, apply Theorem A with B = S and R = O, and get

Cabello and Gajser

|S | ≤ (1 + c s λ -s ) • |O|. For maximization problems, take B = O and R = S , and get |O| ≤ (1+c s λ -s )•|S | or equivalently |S | ≥ (1-c s λ -s )•|O|.

Computational efficiency of geometric local search

Given a parameter ε > 0, local search with radius λ = Θ (ε -1 s ) provides a (1 + ε)approximate solution to problems whose exchange graphs have the separator property with parameter s. This can be implemented in n O(λ ) time by considering all possible local improvements, thus yielding a PTAS in time n O(ε -1/s ) . In particular, this gives a PTAS in time n O(ε -2 ) for the five problems listed in section 1.

The parameterized versions of these problems are W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]-hard: even for unit disks, independent set is W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]-complete [START_REF] Marx | Efficient approximation schemes for geometric problems?[END_REF], dominating set is W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]-hard [START_REF] Marx | Parameterized complexity of independence and domination on geometric graphs[END_REF], and dominating set of unit disks is easily reduced to our other three problems. The details and reductions are explained in section 5. Under the common assumption that FPT W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF], which follows from the exponential-time hypothesis, these problems do not admit PTASs with time complexity poly(n) • f (ε) for any arbitrary computable function f . In other words, the dependence of the exponent of n on ε is necessary.

Still, the running time of local search is prohibitively expensive as soon as λ is greater than 3 or 4. There have been two complementary approaches towards further progress: firstly, careful implementations that find local improvements more efficiently than by brute force [START_REF] Bus | Limits of local search: Quality and efficiency[END_REF]. The second, more structural approach is to better analyze the quality of solutions resulting from local search algorithms, mainly by studying the properties of exchange graphs [3].

Our results

Tightness of Theorem A

Our main result is a construction, given in section 3, showing that Theorem A is asymptotically tight whenever 1 s is an integer.

| = n + o(n) and |B n | ≥ (1 + c d • λ -1 d )|R n | -o(|R n |) as n → ∞.
Furthermore when d = 2 they are Gabriel graphs.

A graph (V, E) is called Gabriel if there exists a mapping f of the vertices of V to points in the plane such that v i , v j ∈ E if and only if the circumdisk of the segment f (v i ) f (v j ) contains no other point of f (V ). Gabriel graphs are subgraphs of Delaunay triangulations and thus planar.

Remark. Since our construction for d = 2 is planar, previous analogues of Theorem A restricted to planar graphs are also tight.

Algorithmic consequences

The analysis of local search in terms of the radius achieving a (1 + ε)-approximation is tight for the five problems listed earlier (which all had s = 1 2 ), as well as for a few other problems with small separators (section 4). Theorem B ( [START_REF] Mustafa | Improved results on geometric hitting set problems[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the minimum hitting set problem for pseudodisks. Corollary 1. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there is a set D of at least n disks and two disjoint sets B and R of at least n points in R 2 each such that both B and R are hitting sets for D, |B| ≥ (1 +Cλ -1

2 )|R| and B is a λ -locally optimal solution to the hitting set problem for D with P = B ∪ R. Theorem C ( [START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the maximum independent set problem for pseudodisks. Corollary 2. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are two independent sets B and R of at least n disks in R 2 such that |B| ≥ (1 +Cλ -1

2 )|R| and R is a λ -locally optimal solution to the independent set problem in B ∪ R. Theorem D ( [START_REF] Aschner | Approximation schemes for covering and packing[END_REF][START_REF] Chan | Exact algorithms and APX-hardness results for geometric packing and covering problems[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the minimum set cover problem for disks. Corollary 3. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are a set P of Θ (|R|) points in R 2 and two sets B and R of at least n disks in R 2 , each covering all of P, and such that |B| ≥ (1 +Cλ -1

2 )|R| and B is a λ -locally optimal solution to the set cover problem for P in B ∪ R. Theorem E ( [START_REF] Gibson | Algorithms for dominating set in disk graphs: Breaking the log n barrier[END_REF][START_REF] Basu Roy | Packing and covering with non-piercing regions[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the minimum dominating set problem for pseudodisks. Corollary 4. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there is a set D of disks in R 2 and two dominating sets B and R of D of at least n disks each such that |B| ≥ (1 +Cλ -1

2 )|R| and B is a λ -locally optimal solution to the dominating set problem for D. Theorem F ( [START_REF] Ene | Geometric packing under non-uniform constraints[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the maximum unit-capacity point-packing problem for disks. Corollary 5. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are two sets B and R of at least n points in R 2 and a set D of Θ (|R|) disks in R 2 such that every disk of D contains one point from B and one point from R, |B| ≥ (1 +Cλ -1

2 )|R| and R is a λ -locally optimal solution to the unit-capacity pointpacking problem for D in B ∪ R.

Borrowing a term from Arya et al.

[4] we could say that: "The locality gap for independent set of disks, dominating set of disks, etc. is 1 +Θ (λ -1/2 )".

Proof of Theorem 1

In this section we build a family of graphs that have the properties stated in Theorem 1. Namely, given parameters d, a large enough λ and n, we construct a bipartite graph G with vertex set (B, R) such that: We define a first bipartite graph G(d, L) as follows. The red vertices of G(d, L) consist of the (L + 1) d points of Ξ . We next place a blue vertex at the center of each of the L d cells of Ξ -except for the lowest cell, which contains two blue vertices with coordinates 1 4 , . . . , 1 4 , 3 4 and 3 4 , . . . , 3 4 , 1 4 . Thus G(d, L) has precisely L d + 1 blue vertices. The edges of G(d, L) consist of 2 d edges from each blue vertex to the 2 d red vertices of its cell. Of the two blue vertices in the lowest cell of Ξ , one is connected to all the red vertices of the cell except for (0, . . . , 0, 1) and the other to all red vertices except for (1, . . . , 1, 0).

1. |R| = n + o(n) as n → +∞, 2. G is λ -expanding, 3. |B| ≥ (1 + cλ -1 d ) • |R| -o (|R|) as n → +∞,

Our second and final graph

G(d, L,t) = (B, R; E) is defined as a t × . . . × t grid composed of t d translates of G(d, L). Each translate of G(d, L) is indexed by a vec- tor τ ∈ {0, . . . ,t -1} d , where G τ denotes the translate of G(d, L) by L • τ.
The blue vertices of G(d, L,t) are simply the disjoint union of the blue vertices of each G τ ; the red vertices are also the union of the red vertices of each G τ , except that we identify duplicate red vertices shared by the boundary of two adjacent grids. See Figure 1 for an example for the case d = 2.

L G 00 G 01 G 02 G 03 G 04 G 10 G 11 G 12 G 13 G 14 G 20 G 21 G 22 G 23 G 24 G 30 G 31 G 32 G 33 G 34 G 40 G 41 G 42 G 43
B = 1 2 , . . . , 1 2 + x : x ∈ {0, . . . ,tL -1} d \ {0, L, . . . , (t -1)L} d (µ, . . . , µ, 1 -µ) + L • x : x ∈ {0, 1, . . . ,t -1} d , µ ∈ 1 4 , 3 4 , E = (b, r) ∈ B × R : min i∈{1,...,d} |x i (b) -x i (r)| ≤ 1 2 , max i∈{1,...,d} |x i (b) -x i (r)| ≤ 1 .
The L d + 1 blue vertices of the translate G τ form the set B τ . For the red vertices, note that the outer red vertices of each translate of G(d, L) may be shared between up to 2 d translates. To avoid this overlap, let R τ consist only of the L d red vertices v ∈ G τ such that x i (v) < L(τ i + 1) for each i. In two dimensions, this amounts to peeling off the 2L + 1 red vertices located on the top and right boundaries of G τ .

Let R b be the set of red vertices with at least one coordinate value equal to tL. We have

B = τ B τ and R = R b ∪ τ R τ ,
where all unions are disjoint. Observe that

|B| = t d (L d + 1) and |R| = (tL + 1) d . (3)
This concludes the construction of G(d, L,t), although the values of L and t are still to be chosen. We now prove that this graph has the desired expansion and separator properties.

Local expansion. To prove that G(d, L,t) is locally expanding, we fix a subset B of B and let R = N(B ) be the set of its (red) neighbors in G(d, L,t). We show that |R | ≥ |B | whenever B is smaller than some function of L and d; later we will set L such that this function turns out to be at least λ .

A grid cell is called non-empty if it contains a vertex of B and otherwise empty. A vertex of R that belongs to R b or whose top cell is empty is called a boundary vertex.

We first sketch a proof in two dimensions based on a charging argument (a oneto-one mapping from B to R ): each vertex of B is charged to a vertex of R such that each vertex of R receives at most one charge, implying that |R | ≥ |B |. To this end charge each vertex of B to the anchor red vertex of its cell. For those G τ containing two blue vertices of B in the lowest cell, one of them remains uncharged. On the other hand, each vertex of R receives one charge, except the boundary vertices which receive zero charge. Now for each τ for which G τ contains at least two boundary red vertices in R , charge the uncharged blue vertex of B in G τ (if it exists) to any one of these (at least two) boundary vertices.

There still remain some uncharged blue vertices, namely one in each of those G τ that have less than two boundary red vertices. However, for each such τ, we show (Lemma 1 below) that G τ must contain at least

= √ n L implies that |R| = n + o (n), |B| = n 1 + 1 L 2 = n 1 +Θ 1 λ 1/2
, and we are done. Now we present the complete proof for general d. We need two preliminary statements, Lemma 1 and Equation 6. Let the indicator variable η τ be 1 if both blue vertices in the lowest cell of G τ belong to B and 0 otherwise. Also let δ τ be the number of boundary vertices in R τ . The total number of boundary vertices in R is thus

δ = |R b ∩ R | + ∑ τ δ τ . ( 4
) Lemma 1. For each index τ, if η τ = 1 and δ τ < 2, then |B ∩ B τ | ≥ L d 2 .
Proof. As B contains both blue vertices from the lowest cell of G τ , R contains the 2 d red vertices of this cell. If δ τ = 0, that is, R τ contains no boundary vertex, then the blue vertex in each of the other cells of G τ is present in B , and so B includes all of B τ , which consists of L d + 1 blue vertices.

It remains to consider the case when R τ contains a unique boundary vertex v r ∈ R ∩ R τ . Without loss of generality, assume that τ = (0, . . . , 0). As both blue vertices from the lowest cell of G τ belong to B , the boundary vertex v r cannot be the lowest vertex of G τ , which has coordinates (0, . . . , 0). Thus there must be some j ∈ {1, . . . , d} for which x j (v r ) > 0. Consider the grid slab Ξ consisting of all cells whose anchor vertex v has x j (v) = 0. Note that Ξ contains the lowest cell of G τ , which has two vertices of B . Thus no other cell of Ξ can be empty, as otherwise that would imply the existence of another boundary red vertex anchoring one of the cells of Ξ . Now take any cell c of Ξ whose anchor vertex differs in at least one coordinate other than x j from v r ; there are L d-1 -1 such cells. All the L cells of G τ whose anchor vertex only differs in the j-th coordinate value from the anchor vertex of c must also be non-empty, as otherwise it would imply the existence of another boundary red vertex in one of these L cells.

Thus there are at least

L L d-1 -1 non-empty cells in G τ , i.e., |B ∩ B τ | ≥ L d -L
which is at least L d 2 since L ≥ 2. Let T be the set of indices τ with η τ = 1 and δ τ < 2. As a consequence of the previous lemma, for every such τ ∈ T , the translate G τ contains at least L d 2 vertices of B , and thus |T | ≤ 2|B |L -d . Now consider the quantity η τ -δ τ 2 . If τ ∈ T , we have η τ = 1 and 0 ≤ δ τ < 2 and so η τ -δ τ 2 is at most 1. Otherwise for any τ / ∈ T , it is 0 or negative. Therefore

∑ τ η τ - δ τ 2 ≤ |T | ≤ 2|B | L d . (5)
An isoperimetric inequality. Consider the set S of all grid cells containing vertices of B . As each cell contains at most two blue vertices, |B | ≤ 2|S|. In the orthogonal projection along the i-th coordinate, i ∈ [d], S is sent to a set S i of (d -1)-dimensional cells. The preimage of each cell of S i is a column of d-dimensional cells. As such, it contains at least one boundary vertex: among its vertices with maximum i-th coordinate, the lexicographically smallest is either in R b or the anchor vertex of an empty cell. Thus the total number δ of boundary vertices is at least |S i |. The combinatorial Loomis-Whitney inequality [START_REF] Loomis | An inequality related to the isoperimetric inequality[END_REF] relates dand (d -1)-dimensional volumes:

d ∏ i=1 |S i | ≥ |S| d-1 ≥ |B | 2 d-1
, from which it follows that

δ d ≥ d ∏ i=1 |S i | ≥ |B | 2 d-1 . (6)
Now we come to the key claim: the graph

G(d, L,t) is (2 1-3d L d 2 )-expanding. Lemma 2. If 2 3d-1 |B | ≤ L d 2 , then |R | ≥ |B |.
Proof. For every index τ, by definition, each vertex in the set R τ ∩ R either has its top cell non-empty or is a boundary vertex of G τ . The number of non-empty top cells in G τ is |B τ ∩ B |η τ , while the number of boundary vertices is δ τ . Thus

|R | = |R b ∩ R | + ∑ τ |R τ ∩ R | = |R b ∩ R | + ∑ τ |B τ ∩ B | -η τ + δ τ = |R b ∩ R | + |B | -∑ τ (η τ -δ τ ) ≥ |B | -∑ τ η τ - δ τ 2 + 1 2
|R b ∩ R | + ∑ τ δ τ = |B | -∑ τ η τ - δ τ 2 + δ 2 ,
with the last equality following from Equation (4). Use the lower bounds Equation ( 5) and Equation ( 6) for the second and third summands to get

|R | ≥ |B | - 2|B | L d + 1 2 |B | 2 (d-1)/d . Now |R | ≥ |B | follows when 2|B | L d ≤ 1 2 |B | 2 (d-1)/d 2 3-1/d |B | 1/d ≤ L d or equivalently 2 3d-1 |B | ≤ L d 2 .
Setting parameters. Given d, λ and n, choose

L = max 2, 2 3d-1 λ 1/d 2 and t = n 1/d L -1 .
Note that L does not depend on n and L d is Θ (λ 1 d ) when λ → +∞. Using Equation (3), we obtain the required bounds on R and B: 2 . See e.g. [START_REF] Conway | Sphere Packings, Lattices and Groups. Grundlehren der mathematischen Wissenschaften[END_REF] for estimates on such bounds.

|R| = (tL + 1) d = n + o(n), |B| |R| = t d L d + 1 (tL + 1) d = 1 + 1 L d + o(1) as n → +∞ ≥ 1 + c d λ -1 d + o n (
Gabriel graph structure. For d = 2, the circumdisk of each blue-red edge in G(d, L,t) contains no vertex but its endpoints, so in this case G(d, L,t) is a Gabriel graph and property ( 5) is proved.

Remark. With the understanding that a one-dimensional cell is an interval, the construction covers the case d = 1. The graph G(1, L,t) is a path of length 2tL + 1, seen as blue-red bipartite, with every L-th blue vertex duplicated. It has |R| = tL + 1 and |B| = t(L + 1) and is (L + 2)-expanding.

Fig. 3: The graph G(1, 3, 3).

Algorithmic consequences

Geometric problems in the plane

We construct arbitrarily large instances of our five optimization problems with a λlocally optimal solution that is a factor of 1 + Ω (λ -1/2 ) worse than the optimal solution. Since our instances consist of disks rather than just families of pseudodisks, the bound applies also to the restrictions of these problems to disk families. For d = 2 and any given λ ≥ λ d and n, let G = (B, R; E) be the planar and λexpanding graph (B n , R n ; E n ) described in Theorem 1 and built in section 3. Our instances are based on G: its vertex sets are associated with feasible solutions of the problems. It then suffices to check that the solution associated with B n (for minimization problems) or R n (for maximization problems) is locally optimal. Corollary 1. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there is a set D of at least n disks and two disjoint sets B and R of at least n points in R 2 each such that both B and R are hitting sets for D, |B| ≥ (1 +Cλ -1

2 )|R| and B is a λ -locally optimal solution to the hitting set problem for D with P = B ∪ R.

Proof. Recall that the circumdisk of each edge of G contains only its two endpoints. The input consists of all such disks, with P = B ∪ R, so that the hitting sets are exactly the vertex covers of G. By construction both B and R are feasible solutions.

On this instance, a λ -local improvement for B would remove a set B of blue vertices with |B | ≤ λ . To preserve the hitting set property, it would then need to add to the solution the red endpoints of all edges with their blue endpoint in B , i.e. the set N(B ). Because the graph is λ -expanding, there are at least |B | such red neighbors, and thus B is λ -locally optimal.

Independent set of pseudodisks

Theorem C ( [START_REF] Chan | Approximation algorithms for maximum independent set of pseudo-disks[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the maximum independent set problem for pseudodisks.

Corollary 2. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are two independent sets B and R of at least n disks in R 2 such that |B| ≥ (1 +Cλ -1

2 )|R| and R is a λ -locally optimal solution to the independent set problem in B ∪ R.

Proof. Realise the graph G as an intersection graph of red and blue disks. (Because it is planar, the disks could even be taken interior-disjoint by the Koebe-Andreev-Thurston theorem [START_REF] Koebe | Kontaktprobleme der konformen abbildung[END_REF].) The independent sets of disks correspond to the independent sets of G. Since G is bipartite both the blue and red families of disks form independent sets, and the red solution is (λ -1)-locally optimal-in maximization terms: a (λ -1)-local improvement for the red solution would remove a set R of up to λ -1 red disks and replace them with a set B of blue disks such that N(B ) ⊆ R (to preserve independence Fig. 5: "Tight" instances for independent set and set cover with disks.

Theorem D ( [START_REF] Aschner | Approximation schemes for covering and packing[END_REF][START_REF] Chan | Exact algorithms and APX-hardness results for geometric packing and covering problems[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the minimum set cover problem for disks. Corollary 3. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are a set P of Θ (|R|) points in R 2 and two sets B and R of at least n disks in R 2 , each covering all of P, and such that |B| ≥ (1 +Cλ -1 2 )|R| and B is a λ -locally optimal solution to the set cover problem for P in B ∪ R.

Proof. As in the proof of Corollary 2, realise G as an intersection graph of blue and red disks. Take for P one point from each blue-red intersection. The set covers for this instance are exactly the vertex covers of G.

Dominating set of pseudodisks

Theorem E ( [START_REF] Gibson | Algorithms for dominating set in disk graphs: Breaking the log n barrier[END_REF][START_REF] Basu Roy | Packing and covering with non-piercing regions[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the minimum dominating set problem for pseudodisks.

Corollary 4. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there is a set D of disks in R 2 and two dominating sets B and R of D of at least n disks each such that |B| ≥ (1 +Cλ -1 2 )|R| and B is a λ -locally optimal solution to the dominating set problem for D.

Proof. The instance that was proposed for set cover (Figure 5b) becomes an instance of dominating set when the points of P are seen as zero-radius disks, i.e. take D = P ∪ B ∪ R. A feasible solution that involves some of the zero-radius disks of P can be transformed into a solution of at most the same cardinality whose support is entirely blue and red since the disks of P are fully included in the other disks. Thus it suffices to examine the efficiency of local search on blue-red solutions. The bluered dominating sets of this instance are exactly the covers of points by blue and red disks.

Constant-capacity packing problems

Our results hold already for the unit-capacity version of these problems.

Theorem F ( [START_REF] Ene | Geometric packing under non-uniform constraints[END_REF]). Local search with radius O(ε -2 ) is a (1 + ε)-approximation algorithm for the maximum unit-capacity point-packing problem for disks.

Corollary 5. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are two sets B and R of at least n points in R 2 and a set D of Θ (|R|) disks in R 2 such that every disk of D contains one point from B and one point from R, |B| ≥ (1 +Cλ -1 2 )|R| and R is a λ -locally optimal solution to the unit-capacity pointpacking problem for D in B ∪ R.

Proof. Take for D the set of all disks associated with the edges, as in the hitting set instance (see Figure 4b). Since every such disk contains only two points of P, the "unit-capacity point-packings" of this instance are exactly the independent sets of G. The result then follows from the analysis in Corollary 2.

The dual problem, defined in [START_REF] Ene | Geometric packing under non-uniform constraints[END_REF], is the unit-capacity disk-packing problem, where we are given a set D of disks and a set P of points and we must return a largest subset of D that covers every point of P at most once. Corollary 6. There is a positive constant C and a positive integer λ 0 such that for every integer λ ≥ λ 0 there is a positive integer n λ such that for every integer n ≥ n λ there are two sets B and R of at least n disks each and a set P of Θ (|R|) points such that every point of P is contained in one disk from B and one disk from R, |B| ≥ (1 +Cλ -1 2 )|R| and R is a λ -locally maximal solution to the unit-capacity diskpacking problem for B ∪ R in P.

Theorem J. There is an absolute constant c > 0 such that, for every given integer λ ≥ 3, any bipartite planar graph on vertex sets (B, R) that is λ -expanding has a matching with at least (1cλ -1

2 )|B| edges.

Now it follows from our constructions that this is tight.

Corollary 9. There are absolute constants c 0 , λ 0 > 0 such that, for every given integer λ ≥ λ 0 , some bipartite, λ -expanding planar graph on vertex sets (B, R) does not have matchings with more than (1c 0 λ -1 2 )|B| edges.

Parameterized hardness and conditional lower bounds

Lower bounds on the possible running time of PTASs for our problems are derived from results in parameterized complexity in the manner of [START_REF] Marx | Efficient approximation schemes for geometric problems?[END_REF].

Every combinatorial optimization problem has a decision version parameterized by k ∈ N, informally "Does the instance have solutions smaller than k (minimization) / larger than k (maximization)?".

If this can be answered in time f (k) n c for some arbitrary computable function f and c ≥ 0, then (the decision version of) the problem is fixed-parameter tractable, or in the class FPT. Parameterized problems that are reducible to the search for a clique of size k in general graphs-under an appropriate notion of reduction-form the class W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]. The inclusion FPT ⊆ W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF] is thought to be proper; this is for example a consequence of the exponential time hypothesis.

Theorem K ([23]). Maximum independent set of unit disks is W[1]-complete. Theorem L ([24]). Minimum dominating set of unit disks is W[1]-hard.
This extends to hitting set by a simple reduction. Recall the definition of the unit-capacity disk-packing problem on page 14.

Corollary 12. Unit-capacity disk-packing is W[1]-hard, even with unit disks.

Proof. Given an instance of independent set with n unit disks, let D consist of these disks and P contain one point from each nonempty pairwise intersection in D. The set P has size O(n 2 ) and can be computed in O(n 2 ). Now the feasible solutions of unit-capacity disk-packing for D and P are exactly the independent sets of D.

Finally the disk-packing problem can be reduced to the point-packing one (defined on page 2).

Corollary 13. Unit-capacity point-packing is W[1]-hard, even with unit disks.

Proof. Given an instance of unit-capacity disk-packing with unit disks D and points P, let D consist one unit disk centerd at each point in P and P contain the centers of the disks in D. The feasible solutions of unit-capacity disk-packing for D and P are exactly the feasible solutions of unit-capacity point-packing for D and P .

An efficient PTAS is a PTAS that runs in time f (ε) n c for an arbitrary function f and c ≥ 0. The following observation first appeared in C. Bazgan's master's thesis [START_REF] Bazgan | Schémas d'approximation et complexité paramétrée[END_REF][START_REF] Cesati | On the efficiency of polynomial time approximation schemes[END_REF].

Theorem M. A combinatorial optimization problem with an integral-valued objective function and an efficient PTAS with f computable is in FPT when parameterized by the value of its solution.

Proof. Given a minimization problem with an efficient PTAS whose running time is f (ε) n c , for each instance we can find in time f (0.5/k)n c a solution with value V such that

1 + 1 2k • OPT ≥ V ≥ OPT. If V ≥ k + 1, then OPT ≥ 2kV 2k + 1 ≥ 2k 2 + 2k 2k + 1 > k,
so computing V answers the question "Does the instance have OPT ≤ k?" in time f (0.5/k)n c , i.e. the problem parameterized by the value of its solution is in FPT.

Since the problems that we consider are W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]-hard, we conclude that none of them admit PTASs with running time f (ε)n O (1) for any computable f unless the inclusion FPT ⊆ W [START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF] is an equality.

Perspectives and open questions

We emphasize that our results apply to standard, non-specialized local-search techniques. Although the approximation quality of a previously successful one-size-fitsall approach cannot be improved, custom algorithms tailored for specific problems can bypass this bound, especially when the exchange graphs are extremely sparse. For example we do not know whether our constructions can be transformed into a local-search-defeating instance for the problem of terrain guarding, a question that can be formulated as follows.

Question. Are the exchange graphs of Gibson et al. [START_REF] Gibson | An approximation scheme for terrain guarding[END_REF] for terrain guarding sparser than other planar graphs? What is the minimum size of their separators?

  + |S ∩ O| |O \ S | + |S ∩ O| , if we prove (say) that |S \ O|/|O \ S | ≤ 1 + ε then this is also true of |S |/|O|. To relate the cardinalities of S and O, a bipartite exchange graph is built on vertex sets S and O with the following local vertex expansion property 1 : Minimization: for all S ⊆ S of size at most λ , |N(S )| ≥ |S |. (1) Maximization: for all O ⊆ O of size at most λ , |N(O )| ≥ |O |.

  where c depends only on d, 4. any subgraph of G on m vertices has a separator of size O(m 1-1 d ), and 5. G is a Gabriel graph when d = 2. The vertices of the set R will be called the red vertices, and the vertices of the set B the blue vertices. Our construction is geometric, in that vertices correspond to points in R d . Thus we use the terminology vertex and point interchangeably. We denote the i-th coordinate of a point p ∈ R d by x i (p). Construction of G. Let L ≥ 2 and t be two positive integers whose values will be fixed later as a function of the parameters d, λ and n. Let Ξ be a L × • • • × L regular integer grid in R d consisting of the (L + 1) d points in {0, . . . , L} d . It has L d cells, each being a unit d-cube defined by precisely 2 d vertices of Ξ . In every cell of Ξ , the vertex with the lexicographically minimum coordinates among the 2 d vertices defining the cell is called the anchor vertex of that cell. Each vertex-apart from those with one of the d coordinate values equal to L-is the anchor vertex of exactly one cell, which is called its top cell. The cell with anchor vertex (0, . . . , 0) is called the lowest cell of Ξ .

Fig. 1 :

 1 Fig. 1: The graph G(d, L) (left, with d = 2 and L = 3) has L d grid cells. It is the basic building block of the graph G(d, L,t) (right, with t = 5). Red vertices are denoted by squares while the blue vertices are denoted by disks.

Fig. 2 :

 2 Fig. 2: The three-dimensional lowest cell of G(3, L).

L 2 2 2 4 2 •

 222 vertices of B . Thus overall, there are at most |B | L 2 /2 = 2|B | L 2 such τ's and therefore at most that many uncharged blue vertices of B . On the other hand, we argue that the total number of boundary red vertices is at least c 2 • |B |, for some constant c 2 (see the isoperimetric inequality below). By our charging scheme, at least half of them, i.e. c 2 2 • |B |, are still uncharged. Thus when 2|B | L 2 ≤ c 2 2 • |B |, or equivalently |B | ≤ c L 4 , the number of uncharged blue vertices will be less than the number of uncharged red vertices. Now setting L = Θ λ 1 4and t

1 )

 1 for λ ≥ λ d , where the positive constants c d and λ d depend only on d. Since 2 1-3d L d 2 ≥ λ , it follows from Lemma 2 that property (2) holds: G is λ -expanding. This achieves the proof of Theorem 1. Finally, the stated separator properties are a consequence of the specific geometric structure of G(d, L,t). Ball graph structure. A ball graph is the intersection graph of a family of n balls in R d and is p-ply if no point in R d belongs to more than p balls of this family. Such graphs have separators of size O(p 1/d n 1-1 d ) [25]. A bounded-ply ball graph is obtained from G(d, L,t) by only adding some edges: put a d-dimensional ball of radius √ d 4 at each vertex of G(d, L,t). The resulting edge set includes that of G(d, L,t)-they coincide when d ≤ 3-so that G(d, L,t) inherits separator properties of ball graphs. In other words, any subgraph of G(d, L,t) on m vertices has a separator of size O(m 1-1 d ) (this is property (4)). Remark. The ply is bounded by a function of d only: each of the balls covering some given point of x ∈ R d is centered on a different vertex of B ∪ R at distance at most √ d 4 of x. In other words, the ply is at most the maximum number of points of B ∪ R inside any ball of radius √ d

  (a) Detail of the graph G used in "bad" instances. (b) Hitting set (drawing only a few disks for readability).

Fig. 4 :

 4 Fig. 4: A tight instance for the hitting set problem.

  ) and |B | > |R |. If there exists a subset B ⊆ B of size |R | + 1, which is at most λ , then since G is λ -expanding such a set has |B | ≤ |N(B )| ≤ |R |, a contradiction. Thus R is a (λ -1)-locally optimal solution. 4.1.3 Set cover for disks (a) Independent set. (b) Set cover.

Corollary 10 .

 10 Minimum hitting set of unit disks is W[START_REF] Agarwal | Independent set of intersection graphs of convex objects in 2D[END_REF]-hard.Proof. Given an instance of dominating set with n unit disks, let P consist of their centers and D consist of the n radius-2 disks centered at P. The hitting sets of D in P are exactly the dominating sets of the initial unit disks.Corollary 11. Minimum set cover by unit disks is W[1]-hard.Proof. Given an instance of hitting set with unit disks D and points P, let P consist of the centers of D and D contain one unit disk centerd at each point in P. The set covers of P in D are exactly the hitting sets of D in P.

For a graph G = (V, E) (which will always be clear from the context) and a set V ⊆ V , N(V ) denotes the set of neighbors of the vertices of V in G.

Acknowledgements We thank the referees of previous versions of this article for several helpful comments.

This work was supported by ANR grant SAGA (JCJC-14-CE25-0016-01) and ANR grant ADDS (ANR-19-CE48-0005). A conference version of this paper was presented at the 34th International Symposium on Computational Geometry (SoCG 2018).

Conflict of interest

The authors declare that they have no conflict of interest.


Antony Costes
email: antony.costes@univ-tlse3.fr

Nicolas A Turpin

David Villeger

Pierre Moretto

Bruno Watier

Influence of Position and Power Output on Upper Limb Kinetics in Cycling

Keywords: inverse dynamics, joint torques, powers, works, standing

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Previous work dedicated to pedaling performance and injury prevention in cycling mainly focused on lower limb biomechanics. [START_REF] Bini | Mechanical work and coordinative pattern of cycling: a literature review[END_REF] However, because the upper limbs may provide significant contributions in trunk support, stabilization, or power transfer to the cranks, [START_REF] Kautz | A comparison of muscular mechanical energy-expenditure and internal work[END_REF] knowledge in regard to upper limb kinetics in cycling could be useful for both performance improvement and clinical applications.

To date, only indirect insights into upper limb actions have been available. Previous studies assessed rider-induced forces and moments on the handlebar and showed that both pattern and magnitude of the crank power, and position (ie, seated or standing), influenced handlebar loadings. At crank power corresponding to ≈200 W, the handlebar forces were always oriented in both the forward and downward directions in a seated position, suggesting that the role of the arms is mainly to support the torso weight. [START_REF] Bolourchi | Measurement of rider induced loads during simulated bicycling[END_REF] Conversely, at crank power higher than 200 W, alternation between pulling and pushing forces on the handlebar have been observed both in seated and standing positions, suggesting that the arms play a different role as crank power increases. [START_REF] Stone | The effect of rider weight on rider-induced loads during common cycling situations[END_REF][START_REF] Poirier | Transition from the classical posture to the upright posture during cycling[END_REF] Upper limb contribution to crank power has never been assessed directly but its role has been suggested by Baker and colleagues. [START_REF] Baker | Power output of legs during high intensity cycle ergometry: influence of hand grip[END_REF] They showed that maximal crank power was lower without handgrip on the handlebar (1136 ± 88 W) in comparison with handgrip (1461 ± 94 W), suggesting that the upper limb may influence the crank power. Nevertheless, hand gripping could influence the lower limbs' performance by inducing greater muscular activations, [START_REF] Turpin | Selective muscle contraction during plantarflexion is incompatible with maximal voluntary torque assessment[END_REF][START_REF] Ebben | The effect of remote voluntary contractions on knee extensor torque[END_REF] suggesting that muscular/mechanical upper limbs' contribution to the crank power needs further verification.

Further insights about the contribution of the upper limbs in cycling have been highlighted through the quantification of energy transfer through the hip joint. Indeed, inverse dynamics models of cycling have shown that crank power could be decomposed into the sum of ankles, knees, hip powers, and hip power transfer. This last term, calculated as the dot product between hip joint linear velocity and hip reaction force, is presumably partly generated by the upper limbs. [START_REF] Kautz | A comparison of muscular mechanical energy-expenditure and internal work[END_REF] One study compared the seated and standing positions and showed higher magnitudes of hip power transfer in a standing position. [START_REF] Caldwell | Movement proficiency: tasks, demands, and constraints[END_REF] In a seated position, power transfer through the hip joint has been reported to represent 5% of the crank power at 540 W, [START_REF] Caldwell | Movement proficiency: tasks, demands, and constraints[END_REF][START_REF] Martin | Joint-specific power production and fatigue during maximal cycling[END_REF] a percentage that could increase with power output (ie, from 3% at 250 W to 8% at about 1000W [START_REF] Elmer | Joint-specific power production during submaximal and maximal cycling[END_REF] ), suggesting that the upper limbs may contribute to crank power.

These indirect evidences prove the importance of the upper limbs' involvement in the cycling movement, however knowledge of the level of upper limb joint moments or upper limb power production in cycling is still lacking. Therefore, the aim of this study was to test the effect of power output and position on the magnitudes of upper limb joint moments, powers, and works. Our hypothesis is that the magnitude of upper limb kinetics could be increased by an increase in crank power output and/or the use of a standing position instead of a seated one.

Methods

Seventeen male students (age: 23.2 ± 3.4 y, height: 1.77 ± 0.06 m, body mass: 73.7 ± 8.8 kg) volunteered to participate in the study. These participants were chosen to avoid expertise effects and were classified as category 4 (recreational) or 5 (athlete noncyclist) cyclists according to Ansley and Cangley's classification (category 1 would be professional cyclists riding more than 30000 km per year and category 6 would be sedentary noncyclists). [START_REF] Ansley | Determinants of "optimal" cadence during cycling[END_REF] Each participant was informed of the experimental procedure and signed an informed consent form before the study. The experimental design of the study was conducted in accordance with the Declaration of Helsinki and approved by the University of Toulouse ethical committee. Participants were asked to avoid high-intensity or exhaustive exercise at least 72 hours before the laboratory trials.

Protocol

The cycling tests were performed using an electromagnetically braked Excalibur (LODE, Groningen, Netherlands). The rate of power output variation imposed by the ergometer was set to 1000 W•s -1 . Participants first performed a cycling test to determine their spontaneous sit-to-stand transition power. This methodology was used in analogy with the walk-run transition to provide different percentages of power output according to a common biomechanical reference for the participants. In this test, phases of 40 seconds at a crank power of 50 W were alternated with phases of 20 seconds with an increment in power. In these 20-second phases, the starting crank power was 200 W, and was incremented by 25 W at each step. This protocol including intervals was chosen after preliminary trials showed that some participants may reach exhaustion before the sit-to-stand transition when using different protocols of crank power increased without recovery. The participants were instructed before the test to maintain a pedaling cadence of 90 revolutions per minute (rpm) provided by a visual feedback. During the test, the participants were encouraged to maintain 90 rpm as soon as their cadence was under or above 90 ± 5 rpm. The sit-to-stand transition power was considered as the crank power at which participants rose from the saddle during at least 10 seconds when they could not maintain 90 rpm in a seated position.

After a 5-minute rest period, participants performed 12 randomized trials in either a seated or standing position at crank power corresponding to 20%, 40%, 60%, 80%, 100%, or 120% of their sit-to-stand transition power. Each pedaling trial recording lasted 10 seconds and was started as soon as the participant was able to steadily pedal at the target crank power at 90 rpm. The pedaling cadence was standardized for all the participants because of its possible influence on the upper limb kinetics. Three minutes of passive rest were allowed between each trial.

Standardized Positioning

To limit bike positioning effects, standardized settings were established. The seat tube angle was set to 73° and the crank length was 0.17 m. The pedal cleat was positioned under the first metatarsal bone. [START_REF] Viker | Shoe cleat position during cycling and its effect on subsequent running performance in triathletes[END_REF] The saddle height was set to obtain a 150° knee angle during full leg extension. The handlebar was flat and positioned to standardize drop and reach lengths according to torso and arm lengths. [START_REF] De Vey Mestdagh | Personal perspective: in search of an optimum cycling posture[END_REF] The positioning of the 2 hands on the handlebar was left up to the participant (handlebar width: 0.7 m, sweep angle: 0°).

Kinematics

Kinematic data from 18 passive markers on the upper limbs were recorded by 12 infrared cameras (VICON, Oxford, UK) at 200 Hz (Figure 1). The anatomical landmarks were selected according to de Leva. [START_REF] De Leva | Adjustments to Zatsiorsky-Seluyanov's segment inertia parameters[END_REF] The wrist and elbow joint centers were defined as the midpoints between the processus styloideus ulnae and radii, and between the lateral and medial epicondyles, respectively. The shoulder joint center was located using the SCoRE method. [START_REF] Ehrig | A survey of formal methods for determining the centre of rotation of ball joints[END_REF] For this method, a specific procedure previously suggested to locate the hip joint center was applied. [START_REF] Begon | Effects of movement for estimating the hip joint centre[END_REF] In a preliminary recording, the participants were asked to repeat shoulder flexion-extension, abduction-adduction, and circumduction. The SCoRE method then allowed the localization of the shoulder joint centers relative to a coordinate system attached to the thorax. Coordinate systems for each of the 3 segments were defined as recommended by the International Society of Biomechanics (ISB). [START_REF] Wu | ISB recommendation on definitions of joint coordinate systems of various joints for the report-ing of human joint motion-Part II: shoulder, elbow, wrist and hand[END_REF] To provide upper limb loadings according to crank angle, 2 additional markers were added on the anterior and posterior part of a strip embedded externally to the pedals to determine the position of each pedal axis.

Handlebar Sensors

The 3D force and moment vectors applied to the handlebar were recorded from 2 tubular sensors (SENSIX, Poitiers, France) positioned on each side of the handlebar (Figure 1C). These dynamometers had a maximum 1% error on each direction (combining linearity and hysteresis errors), and a maximum 1.5% error on the 6 component combination. All measures were given at the sensor reference point, which was localized by 4 reflective markers in the global reference frame. These markers also allowed the localization of the sensor orientation and were fixed to the sensors with a built-in interface.

Inverse Dynamic and Data Analysis

A Newton-Euler recursive algorithm was implemented to perform the bottom-up inverse dynamics protocol used to calculate the 3D joint moments, successively at the wrist, elbow, and shoulder joints (details of the equations in Winter [START_REF] Winter | Biomechanics and Motor Control of Human Movement[END_REF] ). Handlebar reaction forces and moments vectors were translated from the sensor reference point to the wrist joint center using Varignon's formula. Body segments' inertial parameters were derived from the scaling equations given in de Leva. [START_REF] De Leva | Adjustments to Zatsiorsky-Seluyanov's segment inertia parameters[END_REF] Handlebar loadings and upper limb kinematics were synchronized using Nexus 1.7.1 system (VICON, Oxford, UK) and marker position data were filtered using a fourth-order, zerophase-shift, low-pass Butterworth with an 8-Hz cutoff frequency. [START_REF] Mcdaniel | Jointspecific power-pedaling rate relationships during maximal cycling[END_REF] To obtain the joint loadings in function of crank angle, data from a total of 15 pedaling cycles were averaged for each value of crank angle obtained during the pedaling trials of the second part of the study (from 2% to 120% of the sit-to-stand transition power in a random order). Moments applied to the upper limb were the net joint moments at the wrist, elbow, and shoulder, and the external forces were the handlebar reaction force and the joint force acting on the upper arm at the shoulder. Joint moment vectors were expressed according to the segment coordinate systems described in the Kinematics section earlier. External forces and moments developed mechanical energy if they produced or absorbed power during the movement. [START_REF] Aleshinsky | An energy-sources and fractions approach to the mechanical energy-expenditure problem. 2. movement of the multilink chain model[END_REF] Joint powers were calculated at each joint as the product of the joint moment and joint angular velocity, the power transferred across the shoulder joint was computed as the dot product between the shoulder reaction force and its linear velocity, and handlebar power was considered to be zero given the fixed cycling ergometer. [START_REF] Kautz | A comparison of muscular mechanical energy-expenditure and internal work[END_REF] The instantaneous power equation specific to the upper limbs in cycling was therefore:

P t = 1 3 ∑ (Pj) + F sf . V sf = dE l dt , (1)
where P t represents the total upper limb power, P j represents the joint powers, F sf represents the reaction force at the shoulder, V sf represents the shoulder linear velocity, and dE l dt represents the change in mechanical energy of the upper limb. The upper limb network, W UL(NET) , was defined as the mean over 15 complete crank revolutions of the time-integral of the total upper limb power as:

W UL ( NET ) = 1 cycle ∫ [P t t ( ) ] dt = 1 cycle ∫ i=1 6 ∑ [M i t ( ) .ω i (t)] dt + 1 cycle ∫ i=1 2 ∑ [F sf i t ( ) .V sf (t)] dt (2)
where M i and ω i were the i th joint moment and joint angular velocity, respectively. These calculations were performed in the sagittal plane to allow direct comparisons with the power produced at the crank.

To compare the total work of the upper limbs to the total work done at the crank, W UL(NET) was divided by the time-integral of the crank power over a crank revolution (W crank ) to obtain W UL(RELATIVE) : 10,11,20

W UL ( RELATIVE ) = W UL ( NET )
W crank ×100 .

(

) 3
The absolute work done by the upper limbs (W UL(ABSOLUTE) ) during 1 crank revolution was computed as the sum of the absolute value of the work done by the 2 arms and the shoulder transfers, and considers both eccentric and concentric work as positive [START_REF] Winter | Biomechanics and Motor Control of Human Movement[END_REF][START_REF] Van Ingen Schenau | Power equations in endurance sports[END_REF] as:

W UL (ABSOLUTE) = 1 cycle ∫ i=1 8 ∑ P i t ( ) dt = 1 cycle ∫ i=1 6 ∑ M i t ( ). ω i (t) dt + 1 cycle ∫ i=1 2 ∑ F ST i t ( ). V S i (t) dt (4)
The entire data processing was performed using custom-made codes written in Scilab 5.4.0 (SCILAB, Scilab Enterprises, Versailles, France).

Data Reduction and Statistics

Results are reported as mean ± standard deviation. Moments, powers minima and maxima, and works were extracted at each joint for each pedaling condition and these variables were divided by the participant's body mass. Two-way repeated measure ANOVAs (position = seated and standing × crank power = 20%, 40%, 60%, 80%, 100%, and 120% of the sit-to-stand transition power) to test the effect of the position and of the crank power on the upper limb moment, power, and work magnitudes were performed after checking for data normality using Shapiro-Wilk tests and for variance homogeneity using Levene tests. Post hoc analyses were performed using Bonferroni's method. All statistical analyses were performed using the STATISTICA software (STATSOFT, Maisons-Alfort, France). An alpha value of .05 was defined as the level of statistical significance.

Results

The 6 power outputs corresponding from 20% to 120% of the sitto-stand transition power were of 112 ± 19 W (1.6 ± 0.3 W•kg -1 ) for 20%; 225 ± 38 W (3.2 ± 0.6 W•kg -1 ) for 40%; 337 ± 56 W (4.7 ± 0.9 W•kg -1 ) for 60%; 450 ± 75 W (6.3 ± 1.2 W•kg -1 ) for 80%; 562 ± 94 W (7.9 ± 1.5 W•kg -1 ) for 100%; and 675 ± 113 W (9.5 ± 1.8 W•kg -1 ) for 120%. Because the participants could select their mediolateral hand position on the handlebar, which could have affected upper limb kinetics, their hand position across pedaling conditions has been checked. The pedaling condition had no effect on hand position (Table 1). A significant effect of crank power was observed in 16 out of 18 moments analyzed in the seated position and in 14 out of 18 in the standing position, showing that joint moments increased in magnitude with increasing crank power (Figure 234). A significant effect of position was observed, with most of the moments higher in magnitude in standing position in comparison with the seated position.

Normalized moments developed about the wrist, elbow, and shoulder joints across the pedaling cycle at each percentage of the sit-to-stand transition power in the frontal, sagittal, and transverse planes are presented in Figures 2, 3, and4, respectively.

Maximum negative power in the seated position increased for all joints with increasing crank power (Figure 5), whereas maximum positive power increased only at the shoulder joint level. Both negative and positive power was higher in standing position compared with seated position. In standing position, crank power affected shoulder and elbow maximum negative powers, whereas only shoulder maximum positive power increased with increasing crank power.

Net joint work (W UL (NET) ) presented no significant effect of crank power in the seated position (Figure 6A). Conversely, W UL(NET) significantly increased in the standing position at 100% of the sit-tostand transition power in comparison with 20%. W UL(NET) at 120% of the sit-to-stand transition power was significantly higher than all the other crank power conditions. W UL(NET) was significantly higher in the standing position compared with the seated position at 120% of the sit-to-stand transition power.

The total work done by the upper limbs expressed in proportion to work generated at the crank (W UL(RELATIVE) ) ranged from 0.5% to 2% in the seated position and from 1.5% to 2.5% in the standing position (Figure 6B). No significant effect of crank power on upper limbs' total work was observed either in the seated or in the standing position.

The amount of work in absolute value generated by the upper limbs (W UL(ABSOLUTE) ) increased with crank power in both seated and standing positions, with W UL(ABSOLUTE) at 120% of the sit-tostand transition power different from all other crank powers (Figure 6C). W UL(ABSOLUTE) was higher in the standing position than in the seated position at all crank powers.

Discussion

The aim of the current study was to assess, for the first time, upper limb joint loadings in cycling, and to test if these variables were affected by crank powers and pedaling positions. Results showed that increase in crank power led to an increase in magnitude of the upper limb moments in both the seated and standing positions. The crank power value determined in this study was higher than the one of a previous study, reporting 419 ± 30 W as the power above which standing position should be chosen to maximize performance. [START_REF] Hansen | Seated versus standing position for maximization of performance during intense uphill cycling[END_REF] Because Hansen and Waldeland 23 compared times to exhaustion during cycling at different percentage of maximal oxygen uptakes, methodological differences in the criterion defining the optimal sit-to-stand transition power may explain this result.

The increase in upper limb joint moments with increasing power suggests new biomechanical constraints in these conditions. The common point between the variables affected by the crank power was that they were associated with handlebar pulling, whereas the variables not affected were mostly associated with handlebar pushing. Previous studies confirm this evolution of handlebar actions with increasing power. [START_REF] Bolourchi | Measurement of rider induced loads during simulated bicycling[END_REF][START_REF] Stone | The effect of rider weight on rider-induced loads during common cycling situations[END_REF][START_REF] Poirier | Transition from the classical posture to the upright posture during cycling[END_REF] However, why handlebar pulling magnitudes increase with increasing crank power, but not handlebar pushing, is still unclear. A first hypothesis could be that cyclists activate their upper limb muscles to better activate their lower limb muscles. [START_REF] Turpin | Selective muscle contraction during plantarflexion is incompatible with maximal voluntary torque assessment[END_REF][START_REF] Ebben | The effect of remote voluntary contractions on knee extensor torque[END_REF] This could explain the increase in handlebar pulling, but not the stability in handlebar pushing. Another explanation could be found in the main goal of the cycling task: producing crank power. When this constraint increases, it is necessary for a given cadence to produce higher pedal force and thus more vertical force. At one point, these vertical pedal forces may counterbalance the body weight. This finding is consistent with the observation of a reduction of the saddle vertical force with increasing crank power. [START_REF] Poirier | Transition from the classical posture to the upright posture during cycling[END_REF][START_REF] Costes | A reduction of the saddle vertical force triggers the sit-stand transition in cycling[END_REF] The observed increase in handlebar pulling may be used to avoid body elevation when the pedal vertical forces exceed the body weight. Therefore, the increase in upper limb joint moments may allow the performance by trunk stabilization. Given the fact that experts develop higher crank power outputs 25 and that they have been observed to push more and pull less on the pedal than less-trained cyclists, [START_REF] Coyle | Physiological and biomechanical factors associated with elite endurance cycling performance[END_REF] pedaling in a seated position for this population may imply higher levels of upper limb loadings, because of the necessary higher handlebar pulling to remain seated. Studies assessing maximal upper limb moments in isolated joint testing reported higher magnitudes than the one observed in our study. [START_REF] Holzbaur | Moment-generating capacity of upper limb muscles in healthy adults[END_REF][START_REF] Delp | Maximum isometric moments generated by the wrist muscles in flexion-extension and radial-ulnar deviation[END_REF] This comparison suggests that, in cycling, upper limb joint moments may not reach the maximum magnitude possible. However, it cannot be ruled out that the upper limb muscles may face important demands in force given the specific context of pedaling and the likely nonoptimal position for each joint to produce moments, and because of the decrease in joint torque production associated with the increase in joint angular velocity. [START_REF] Anderson | Maximum voluntary joint torque as a function of joint angle and angular velocity: Model development and application to the lower limb[END_REF] In this sense, previous findings showed that myoelectrical activity of the forearm muscles is close to maximal during maximum power pedaling. [START_REF] Baker | Power output of legs during high intensity cycle ergometry: influence of hand grip[END_REF] To improve performance by creating high pedal forces with limited trunk movements, and to avoid the standing position to decrease aerodynamic drag, [START_REF] Martin | Modeling sprint cycling using field-derived parameters and forward integration[END_REF] Note. Mean ± SD position of the center of the left hand on the mediolateral axis. "Absolute" represented the horizontal distance in m between the hand center (defined as the midpoint between the wrist joint center and the midpoint between the 2 metacarpal heads) and the handlebar center. "Relative" represented the difference in m between the hand center in the seated 20% condition and the hand center in the assessed condition. No significant difference was observed between pedaling conditions. and standing cycling (dotted black line) are represented ± one standard deviation (dark gray shading for seated/light gray shading for standing). Data are normalized by body mass over 15 pedaling cycles at 90 revolutions per minute (rpm). ABD = abduction; ADD = adduction. * Significant difference between maximum seated and standing position. $ Significant difference between minimum seated and standing position. ABCDEF indicate a significant difference compared with 120%, 100%, 80%, 60%, 40%, and 20% of the power output corresponding to the sit-to-stand transition for the maximum magnitude in the seated position; abcdef indicate a significant difference compared with the minimum magnitude in seated position; I,II,III,IV,V,VI indicate a significant difference compared with maximum magnitude in the standing position; and 1,2,3,4,5,6 indicate a significant difference compared with minimum magnitude in the standing position.

η 2 sit = eta-squared in the seated position.

η 2 std = eta-squared in the standing position. implication of these results may be the use of strength conditioning programs involving the upper limbs and focusing on the muscular actions associated with handlebar pulling. The mechanical energy cost of the upper limbs was represented in our study by measurement of W UL (ABSOLUTE) , which cumulates values of work associated with both concentric and eccentric contractions. The increased W UL (ABSOLUTE) could be associated with an increase in metabolic cost with increasing crank power. This result is in line with one study which demonstrated a significant reduction in metabolic cost when the torso was stabilized to decrease upper limb actions in cycling. [START_REF] Mcdaniel | Torso stabilization reduces the metabolic cost of producing cycling power[END_REF] The study by McDaniel and colleagues suggested that upper limbs represented about 2% of the pedaling energy cost. However, their study was limited in the crank power they could impose on their subjects (maximum 250 W). From the increase in joint moments and powers observed in our results for power outputs > 250 W, it could be expected that the absolute value of the metabolic cost due to the upper limbs would be higher for higher power outputs. Previous studies showed increasing magnitudes of hip transfer power in the standing position [START_REF] Caldwell | Movement proficiency: tasks, demands, and constraints[END_REF] and with increasing crank power from 3% of the pedal power at 250 W to 8% at about 1000 W. [START_REF] Martin | Joint-specific power production and fatigue during maximal cycling[END_REF][START_REF] Elmer | Joint-specific power production during submaximal and maximal cycling[END_REF] However, the relative upper limb work generation, W UL(RELATIVE) , remained low in both positions and lower than the reported data on hip power transfer. That could mean that other parts of the body such as the back and/or the contralateral leg could participate in the power transmitted through the hip joint force, and that the upper limb direct contribution to the crank power remains low. Further investigations using inverse dynamics with instrumented pedals and seats and lower limb kinematic reconstruction are needed to confirm that the upper limbs could only be partially responsible for the so-called hip transfer power in the literature. These considerations related to moments and works created by the upper limbs suggest that future models should consider both upper and lower limbs when modeling cycling biomechanics and energy expenditures, especially when the focus is on high crank power, elite athletes, and/or on the standing position.

It is important to note that pedaling on a cycling ergometer and cycling in the field are 2 different things. [START_REF] Bertucci | Gross efficiency and cycling economy are higher in the field as compared with on an axiom stationary ergometer[END_REF] Even if the former is a common practice for rehabilitation and training, it does not allow lateral bicycle oscillations, which are supposed to interfere with the pedaling technique. Thus, upper limb kinetics may presumably be modified in the field, particularly in the standing position in which roll angles up to 24° have been observed and may increase the upper limb moments specifically in the frontal plane. [START_REF] Bertucci | Differences between sprint tests under laboratory and actual cycling conditions[END_REF] Other factors such as slope or vibrations may have effects on the upper limb kinetics, in addition to other handlebar systems like road or time-trial, with other drop and reach settings. To test these effects, sensors recording full-body kinematics, and three-dimensional loads applied on each of the bicycle's supports are necessary to provide inverse dynamics analyses of cycling in field conditions. These methods often used to provide insights into the biomechanical causes of the observed movement are limited in accuracy by the combination of kinetic, kinematic, and anthropometric errors, however these sources of error should not change the conclusion about both position and crank power having an effect on upper limb kinetics. Further studies are necessary to fully understand which parameters are leading a cyclist to spontaneously transit from seated to the standing position.

In summary, this study measured three-dimensional moments, powers, and works done at the upper limb joints for various position and crank power conditions. We conclude that upper limb kinetics are affected by both crank power and the pedaling position. By providing a first reference of upper limb kinetic measurements, and by showing that these variables are affected by both the power output and the cycling position, these results have implications for clinicians, athletes, coaches, and sport scientists aiming to enhance performance and prevent injuries in cycling.

Figure 1 -

 1 Figure 1 -(A) Sagittal view of the marker set used to reconstruct the upper limb kinematics. (B) Frontal view. The arrows represent the reaction forces recorded by the handlebar sensors and the dots represent the passive markers used to model the bone movements and orientations. (Figures made with Opensim3.2 software. 34 ) (C) Handlebar with 6-component sensors and the marker set used to locate the sensor origins and orientations; x, y, and z represent the anteroposterior, mediolateral, and vertical axis, respectively.

  Figure 1 -(A) Sagittal view of the marker set used to reconstruct the upper limb kinematics. (B) Frontal view. The arrows represent the reaction forces recorded by the handlebar sensors and the dots represent the passive markers used to model the bone movements and orientations. (Figures made with Opensim3.2 software. 34 ) (C) Handlebar with 6-component sensors and the marker set used to locate the sensor origins and orientations; x, y, and z represent the anteroposterior, mediolateral, and vertical axis, respectively.

  l

Figure 2 -

 2 Figure 2 -Frontal plane moments in the joint coordinate systems for the left upper limb at the wrist, elbow, and shoulder in function of the right crank angle. Mean seated cycling (solid black line)

Figure 3 -

 3 Figure 3 -Sagittal plane moments in the joint coordinate systems for the left upper limb at the wrist, elbow, and shoulder in function of the right crank angle. Mean seated cycling (solid black line)and standing cycling (dotted black line) are represented ± one standard deviation (dark gray shading for seated/light gray shading for standing). Data normalized by body mass over 15 pedaling cycles at 90 revolutions per minute (rpm). FLEX = flexion; EXT = extension. * Significant difference between maximum seated and standing position. $ Significant difference between minimum seated and standing position. ABCDEF indicate a significant difference compared with 120%, 100%, 80%, 60%, 40%, and 20% of the power output corresponding to the sit-to-stand transition for the maximum magnitude in the seated position; abcdef indicate a significant difference compared with the minimum magnitude in seated position; I,II,III,IV,V,VI indicate a significant difference compared with maximum magnitude in the standing position; and 1,2,3,4,5,6 indicate a significant difference compared with minimum magnitude in the standing position.

  -squared in the seated position.η 2 std = eta-squared in the standing position.

Figure 4 -

 4 Figure 4 -Transverse plane moments in the joint coordinate systems for the left upper limb at the wrist, elbow, and shoulder in function of the right crank angle. Mean seated cycling (solid black line) and standing cycling (dotted black line) are represented ± one standard deviation (dark gray shading for seated/light gray shading for standing). Data normalized by body mass over 15 pedaling cycles at 90 revolutions per minute (rpm). EXT = external rotation; INT = internal rotation. * Significant difference between maximum seated and standing position. $ Significant difference between minimum seated and standing position. ABCDEF indicate a significant difference compared with 120%, 100%, 80%, 60%, 40%, and 20% of the power output corresponding to the sit-to-stand transition for the maximum magnitude in the seated position; abcdef indicate a significant difference compared with the minimum magnitude in seated position; I,II,III,IV,V,VI indicate a significant difference compared with maximum magnitude in the standing position; and 1,2,3,4,5,6 indicate a significant difference compared with minimum magnitude in the standing position.η 2 sit = eta-squared in the

Figure 5 -

 5 Figure5 -Powers in the sagittal laboratory plane for the left upper limb at the wrist, elbow, and shoulder in function of the right crank angle. Mean seated cycling (solid black line) and standing cycling (dotted black line) are represented ± one standard deviation (dark gray shading for seated/light gray shading for standing). Data normalized by body mass over 15 pedaling cycles at 90 revolutions per minute (rpm). GEN = power generation; ABS = power absorption. * Significant difference between maximum seated and standing position. $ Significant difference between minimum seated and standing position. ABCDEF indicate a significant difference compared with 120%, 100%, 80%, 60%, 40%, and 20% of the power output corresponding to the sit-to-stand transition for the maximum magnitude in the seated position; abcdef indicate a significant difference compared with the minimum magnitude in seated position; I,II,III,IV,V,VI indicate a significant difference compared with maximum magnitude in the standing position; and 1,2,3,4,5,6 indicate a significant difference compared with minimum magnitude in the standing position.

  -squared in the seated position.η 2 std = eta-squared in the standing position.

Table 1 Hand position across pedaling conditions

 1 one

		20%	40%	60%	80%	100%	120%
	Seated
	Absolute	0.254 ± 0.031	0.256 ± 0.028	0.252 ± 0.028	0.253 ± 0.024	0.250 ± 0.027	0.251 ± 0.028
	Relative	0 ± 0	0.002 ± 0.017	-0.002 ± 0.016	-0.001 ± 0.018	-0.003 ± 0.016	-0.003 ± 0.014
	Standing
	Absolute	0.259 ± 0.021	0.258 ± 0.024	0.264 ± 0.023	0.259 ± 0.021	0.257 ± 0.026	0.262 ± 0.023
	Relative	0.005 ± 0.026	0.004 ± 0.022	0.010 ± 0.022	0.005 ± 0.024	0.003 ± 0.023	0.008 ± 0.022

Acknowledgments

Antony Costes was funded by a PhD grant from the French Ministry of Education and Research (Ministère de l'Education et de la Recherche).

(B) W UL(RELATIVE) . (C) W UL(ABSOLUTE) .

Power output from 20% to 120% of the sit-to-stand transition power correspond to 76 ± 13 J (1.1 ± 0.2 J•kg -1 ), 151 ± 26 J (2.1 ± 0.4 J•kg -1 ), 227 ± 39 J (3.2 ± 0.6 J•kg -1 ), 302 ± 52 J (4.2 ± 0.8 J•kg -1 ), 378 ± 65 J (5.3 ± 1 J J•kg -1 ), and 453 ± 78 J (6.3 ± 1.2 J•kg -1 ) works generated at the cranks by pedaling cycle, respectively. # Significant difference compared with seated cycling (P < .05). a,b,c,d,e Significant difference compared with 20%, 40%, 60%, 80%, and 100% of the sit-to-stand transition power, respectively.

The authors have no financial or personal relationships with other people or organizations that could have inappropriately influenced this research.


B Watier

D Villeger

A Costes

P Moretto

A preliminary study suggests that walk-to-run transition is consistent with mechanical optimization

Keywords: Walk, run, transition, optimization, mechanical cost function

Introduction

In spite of the apparent simplicity, the organization of the neuromusculoskeletal system during complex movements remains poorly understood in humans. One explanation is that the motor system is redundant: a given movement can be realized using different muscles and joint activity patterns (Bernshteĭn 1967). Some theories, such as optimal control or motor primitives, explain this conundrum which pertains to very basic movements, such as grasping or pointing. However, to the author's knowledge, no cost functions have investigated the walking and running coordination during locomotion. While walking is commonly observed at low speed (Froude = Fr = v 2 / gl < 0.5; with v the speed, g the gravity and l the CoM height) and running at high speed, it remains unknown whether a mechanical cost function can explain the change of gait observed. Furthermore, the trigger of the walk-to-run transition has yet to be determined. Classical optimization rules have previously revealed underlying organization of human motion: minimum torque, minimum kinetic energy, or minimum jerk (Flash & Hogan 1985) can predict kinematics of the segments. Similarly, Gonzales and Hull (1989) proposed that a moment cost function (MCF) based on lower limb's joint moments may be a criterion to optimize bicycle settings and pedaling cadence. Using this criterion, Marsh et al. (2000) have shown a link between minimization of the MCF and preferred cycling cadence. Likewise, Poirier et al. (2007) have shown that this criterion can explain the sit-to-stand transition in cycling.

Therefore, the aim of this study was to compute MCF at different walking and running speeds. We hypothesized that MCF would be optimal at low speeds during walking and at high speeds during running.

Methods

Participants and materials

Nineteen healthy men (23 ± 5 y; 1.79 ± 0.07 m; 80.7 ± 11 kg) participated in this experimentation.

They were equipped with 42 reflective markers recorded by 12 optoelectronic cameras sampled at 200 Hz (VICON, Oxford's metrics, Oxford, UK). The participants performed barefoot walking and running tests on a treadmill (PF 500 CX, PRO FORM, Villepreux, France) mounted on a large force platform recording at 1 kHz (AMTI, Watertown, MA, USA). The kinematic and kinetic data were filtered with a 4th-order zero-lag Butterworth filter and with a 6 and 10 Hz cut-off frequency, respectively.

Experimentation

The participants were asked to walk and run with their preferred step frequency at 0.56, 1.11, 1.67, and 2.22 m s -1 and 1. 67, 2.22, 2.78, 3.33, 3.89, and 4.44 m s -1 , respectively. From these tests, Fr was computed for each speed stage i and each participant j as:

Assessed parameters

In the present study, the human body was considered as a whole of 16 rigid body segments (de Leva 1996). The functional centers of rotation of the hips were determined using the SCoRE method.

Merging kinematics, kinetic, and anthropometric data according to de Leva (1996), a Newton-Euler recursive algorithm was used to perform a bottom-up inverse dynamics protocol in order calculate 3D joint moments

Fr ij = 𝜈 2 i g ⋅ l j CONTACT B. Watier
bruno.watier@univ-tlse3.fr

Thus, the MCF must also be considered carefully as it does not take into account the travelled distance. It integrates joint moments during one cycle whose duration is not the same between walking and running. To summarize, the present study shows that the walk-to-run transition optimizes MCF for the duration of one cycle.

Conclusions

This study aimed to determine a cost function which could explain the walk-to-run transition. In accordance with optimal control theory, the present data suggest that the MCF may trigger the walk-to-run transition. at the ankles, knees, and hips. The MCF was then computed as:

where M A (ij), M K (ij), and M H (ij) are the three-dimen- sional joint moments at ankle, knee, and hip at the ith frame and j side, and N is the frame number during one gait cycle. The MCF was expressed in a dimensionless form as MCF D to remove the anthropometric effects from CoM height (l), body mass (m), and gravity (g): MCF D = MCF/ (lmg) (Villeger et al. 2014).

Statistics

MCF D was calculated for each condition (MCF D R and MCF D W for running and walking, respectively) and at each speed stage. Linear regressions were calculated for both locomotion modes to express the dimensionless MCF according to Fr.

Results and discussion

MCF D

R and MCF D W at each speed stage are presented in Figure 1.

For each condition, linear regressions were:

Our results showed that MCF is lower when walking at Fr < 0.49 and during running at higher values of Fr. Although no spontaneous speed transition was determined in this study, this result is close to the spontaneous dimensionless transition speed value reported in the literature: according to Alexander (1989), the walk-to-run transition occurred at Nfr = 0.48 This therefore suggests that our participants were likely to minimize their MCF during gait.

While previous studies proposed that the metabolic energy consumption is not optimal because the preferred transition speed is lower than the optimal transition speed (Tseh et al. 2002), our results confirm that the MCF, a mechanical-based criterion, appears to be a relevant parameter and can predict the locomotion pattern. Otherwise, MCF criterion is computed from joint moments and directly linked with muscular efforts at lower limbs, which have been prove to be well perceived by the central nervous system (Windhorst 2007). Other authors suggest that the determinants of the walk-to-run transition can be instantaneous values like peak moment, peak power (Pires et al. 2014) or peak force (Raynor et al. 2002). Here, MCF is consistent with global optimization as it takes into account whole joint moments at lower limbs during one gait cycle.

Figure 1 .

 1 Figure 1. Dimensionless moment cost function according to Froude number (walking condition in blue and running in red).

View publication stats