Método del Calibre Giratori

Método del Calibre Giratori

Seqüència de mides preses entre parells antipodales del tancament convexo d'un polígon generades en el Método del Calibre Giratori.

En Geometria computacional, el Método del Calibre Giratori (en anglés, Rotating Caliper) és un método usat per a construir algoritmes eficients per a varis problemes, com el diàmetro d'un conjunt de punts o Major distància entre dos polígons convexos.

Història

El método va ser usat per primera volta per Michael Shamos en 1978 per a determinar tots els parells de punts antipodales d'un polígon convexo. El terme rotating caliper va ser falcat en 1983 pel matemàtic Godfried Toussaint qui va aplicar este enfocament a atres problemes dins de la geometria computacional. El nom ve de l'analogia entre esta tècnica i anar rotando una ferramenta de medició el nom de la qual és Calibre de Vernier (conegut com a peu de rei dins d'alguns països de parla hispana) al voltant de la part exterior d'un polígon convexo.

Esta tècnica l'explicarem a través del problema de determinar tots els parells de punts antipodales d'un polígon convexo.

Definicions i conceptes

Un parell de vèrtiços antipodales i el seu corresponent parell de rectes paraleles soport.

Definició 1: Recta soport d'un conjunt de punts S és aquella que passa per un punt del conjunt i deixa a tot S en un dels 2 semiplanos que delimita.

Definició 2: Paraleles soport són 2 rectes de soport paraleles.

Definició 3: Dos punts de S es diuen antipodales si per ells passen paraleles soport, és dir, si podem traçar un parell de rectes que passen cada una per un dels punts, siguen paraleles entre sí i continguen a tots els punts de S en l'espai entre abdós rectes.

Vore també

• en:Convex polygon
• en:Convex hull
• en:Smallest enclosing box