## Entropy and complexity of a path in sub-Riemannian geometry

ENSTA, Unité de Mathématiques
Appliquées, 32 boulevard Victor, 75739 Paris, France;
fjean@ensta.fr.

Received:
18
July
2002

Revised:
27
February
2003

We characterize the geometry of a path in a sub-Riemannian manifold
using two metric invariants, the entropy and the complexity.
The entropy of a subset *A* of a metric space is the minimum number of
balls of a given radius *ε* needed to cover *A*.
It allows one to compute the Hausdorff dimension in some cases and
to bound it from above in general.
We define the complexity of a path in a sub-Riemannian manifold as the
infimum of the lengths of all trajectories contained in an
*ε*-neighborhood of the path, having the same extremities as the
path.
The concept of complexity for paths was first developed to model the
algorithmic complexity of the nonholonomic motion planning problem in
robotics. In this paper, our aim is to estimate the entropy, Hausdorff dimension and
complexity for a path in a general sub-Riemannian manifold.
We construct first a norm on the tangent space
that depends on a parameter ε > 0.
Our main result states then that the entropy of a path is equivalent to the
integral of this *ε*-norm along the path.
As a corollary we obtain upper and lower bounds for the Hausdorff
dimension of a path.
Our second main result is that complexity and entropy are equivalent
for generic paths.
We give also a computable sufficient condition on the path for this
equivalence to happen.

Mathematics Subject Classification: 53C17

Key words: Complexity / Hausdorff dimension / metric entropy / non-linear control / nonholonomic systems / sub-Riemannian geometry.

*© EDP Sciences, SMAI, 2003*