Une technique algorithmique géométrique qui traite des polygones convexes en sim ulant une paire de calibres antipodaux tournant autour du polygone pour repérer les directions de soutien extrémales, calculer diamètres, largeurs, rectangles d'encombrement de surface minimale et autres métriques extrémales en temps linéaire ou quasi-linéaire.

Principe

Maintenir un ensemble constant de points de contact antipodaux (paires de calibres) et les avancer de façon synchrone selon les pentes des arêtes du polygone de sorte que chaque direction de soutien soit rencontrée une fois ; les valeurs extrémales se produisent aux configurations de contact rencontrées durant la rotation continue.

Démonstration

Pour un polygone convexe donné par ses sommets en ordre anti-horaire, placer quatre calibres orthogonaux sur des arêtes supports antipodales et les faire tourner en avançant vers le sommet suivant quand la droite support change de pente ; suivre la distance maximale entre calibres opposés permet de calculer le diamètre en O(n) après le calcul de l'enveloppe convexe.

Mauvaise application

Appliquer la méthode directement à des polygones non convexes ou à des nuages de points sans prendre d'abord l'enveloppe convexe ; cela peut faire manquer des extrêmes locaux ou produire des diamètres erronés car les hypothèses d'antipodalité échouent dans les concavités.

Conséquence

Lorsqu'elle est appliquée aux polygones convexes, elle fournit des temps de calcul optimaux ou quasi-optimaux pour de nombreuses requêtes géométriques extrémales (diamètre, largeur, rectangle d'aire minimale), transformant une optimisation globale continue en une suite finie de mises à jour discrètes.

Inversion

Fixer les calibres à des directions arbitraires et échantillonner des orientations discrètes au lieu de les faire tourner continûment ; cette inversion peut faire manquer des configurations extrémales exactes et ne produit que des estimations approximatives ou dépendantes des directions, sans garanties d'extrême.

Limite

Exige la convexité (ou une réduction préalable à l'enveloppe convexe) et une représentation polygonale avec des sommets ordonnés ; elle ne s'étend pas directement aux polytope s de dimension supérieure sans modifications importantes et une définition soignée de l'antipodalité.

Tension sémantique

Souvent comparée au balayage naïf des paires antipodales ou aux arguments avec droites supports tournantes ; la tension apparaît avec les méthodes à deux pointeurs ou de balayage — les calibres tournants exploitent la géométrie de la convexité pour réduire le nombre de mises à jour mais restent plus spécialisées que les techniques de balayage générales.

Synthèse

Les calibres tournants convertissent l'optimisation par direction continue sur des polygones convexes en une rotation synchronisée discrète de points de contact antipodaux ; en tirant parti de la convexité et de l'ordre des arêtes, ils trouvent efficacement des métriques extrémales globales tout en échouant hors de leur domaine convexe.