Le nombre de recouvrement N(ε,S,ρ) d'un ensemble S dans un espace métrique (X,ρ) est le nombre minimal de boules fermées de rayon ε (pour ρ) dont l'union contient S ; il quantifie combien de « patchs » de rayon ε sont nécessaires pour recouvrir S.

Principe

Mesurer la complexité en comptant les éléments de rayon ε minimaux qui couvrent l'ensemble : les recouvrements convertissent l'étendue géométrique en un compte discret dépendant de ε et de la métrique.

Démonstration

Pour le cube unité [0,1]^d avec la métrique euclidienne, le nombre de recouvrement pour petit ε se comporte comme environ (1/ε)^d : on peut couvrir le cube par O((1/ε)^d) boules (ou cubes) alignés aux axes, illustrant la dépendance à la dimension ambiante.

Mauvaise application

Considérer le nombre de recouvrement calculé avec une métrique comme invariant au changement de métrique ou utiliser un ε trop grand pour déduire la complexité à petite échelle (par ex. employer un ε grossier pour inférer une complexité fine).

Conséquence

Des nombres de recouvrement finis pour de petits ε indiquent une compacité effective et un contrôle de la capacité ; ils interviennent directement dans les bornes de convergence uniforme, les pénalités de sélection de modèle et les estimations d'erreur de discrétisation.

Inversion

Passer à la notion duale de nombre d'empaquetage (packing) ou considérer le problème inverse du plus grand ε pour lequel un nombre donné de boules suffit à recouvrir S.

Limite

Dépend entièrement de la métrique choisie, de la forme des boules et du rayon ε ; les ensembles infinis dans des métriques non discrètes peuvent avoir des nombres de recouvrement infinis pour de petits ε, et le nombre de recouvrement ignore la géométrie du chevauchement au-delà du comptage.

Tension sémantique

Tension avec le nombre d'empaquetage et avec les notions de dimension (Hausdorff, Minkowski) ; deux ensembles ayant des nombres de recouvrement similaires pour un ε peuvent se comporter très différemment à d'autres échelles ou sous d'autres métriques.

Synthèse

Le nombre de recouvrement réduit un ensemble métrique-géométrique à une statistique de comptage : le nombre minimal de boules d'ε nécessaires pour couvrir S, offrant une mesure dépendante de l'échelle et de la métrique de compacité ou de complexité.