Sea P un polígono convexo de n vértices. El diámetro de P se define de manera análoga

Se dice que dos vértices p, q de P son antípodas si existen dos rectas paralelas distintas que pasen por sendos puntos y son soporte de P.

1. Hallar todos los pares de antípodas de P
2. Hallar la distancia entre los puntos de cada par.
3. Quedarse con el mayor valor.

Queda pendiente saber cuanto cuesta encontrar esas N parejas de antípodas y como hacerlo. La respuesta es que no mucho y que el método para encontrarlos ya esta inventado. Pensemos en el convexo P como una tuerca un poco irregular. Para hallar su diámetro, los mecánicos lo que hacen es usar un calibre, en una vuelta de calibre, determinan cual es la mayor abertura del calibre.

Matemáticamente, esta herramienta mecánica vendrá modelizado por un par de rectas paralelas que dejan al polígono en la banda que determinan, es decir, para cada recta el polígono queda en el semiplano en el que esta la otra recta. Y además queremos que esas rectas sean soporte del polígono.

Para un polígono P siempre hay un par de rectas con esas características muy fáciles de hallar: basta considerar las rectas verticales que pasan respectivamente por los vértices de abscisa mínima y abcisa máxima. Para encontrar ahora otro par basta rotar ambas rectas el mismo ángulo, y en el mismo sentido, cada una en torno al punto de apoyo sobre el polígono. Así se consigue que sigan siendo rectas paralelas pero para que además sean soporte de P hay que vigilar el tamaño del ángulo de giro y, en caso de que hubiera mas de un punto de apoyo de P para alguna de esas rectas, decidir en torno al cual se gira.

Para resolver todo eso, comenzaremos dando a cada una de las rectas soporte paralelas una orientación distinta. Por ejemplo a la recta vertical que pasa por Xmin la orientación del eje OY- y la otra la del eje OY+. A cada una de estas rectas orientadas las llamaremos calibre. Si sobre alguna de estas rectas hubiera mas de un vértice de P consideraríamos como centro de giro él ultimo en la dirección del calibre. Esos puntos de apoyo de los calibres serán la primera pareja de antípodas.

A continuación giramos los calibres para detectar otra pareja. El ángulo de giro de los calibres para que el resultado sea de nuevo un par de rectas soporte viene limitado por la frontera de P. Como P es convexo tan solo hay que vigilar el lado adyacente al vértice de apoyo de cada calibre. Por tanto, el ángulo que han de girar ambas rectas para que las resultantes sean también soporte de P viene determinado por el menor de los ángulos que forman cada uno de los calibres con el lado adyacente a su vértice de apoyo en P, tomando el ángulo en sentido positivo respecto da la dirección del calibre. Obsérvese que al girar ese ángulo al menos uno de los calibres se apoya n un lado de P: aquel que daba el ángulo mínimo. Ese calibre girara ahora entorno al nuevo vértice encontrado y ese vértice junto con el otro en el que se apoya el otro calibre determinan una nueva pareja de vértices antípodas. Si los dos ángulos examinados son iguales una vez girados los calibres, ambos quedan apoyados sobre lados paralelos de P y entonces hay tres parejas nuevas de antípodas. Para una mejor observación del algoritmo dibújese un polígono convexo en el siguiente aplet.

De esta manera girando los calibres y recopilando todas las parejas de antípodas que encontremos conseguiremos todas las posibles. La pregunta natural que surge ahora es: ¿hasta cuando hay que girar para tener la seguridad de tenerla todas? La respuesta es fácil: hasta que recomiencen a repetirse. Esto ocurre cuando ambos calibres han girado un ángulo total de a lo mas p, es decir, se han invertido las posiciones iniciales de los calibres y se apoyan sobre la pareja inicial de antípodas.

A lo largo del algoritmo llamaremos C1 y C2 al par de calibres que rotan, p y q los vértices de P donde respectivamente se apoyan y respecto de los cuales giran.

Paso 1: Localizar en P los puntos mínimo y máximo con orden lexicográfico: Xmin y Xmax.

Paso 2: Inicializar p:=Xmin, q:=Xmax y los calibres C1 con la recta vertical que pasa por p con la dirección OY- y C2 con recta vertical que pasa por q y dirección OY+.

Paso 3: Mientras el par(p,q)¹ (Xmax,Xmin) repetir:

En la practica no es preciso hallar el valor de ningún ángulo sino que la comparación entre a y b puede realizarse simplemente utilizando cálculos de áreas signadas tal y como muestra la figura.

a <b Û D (p,SIG(p),x)<0, donde x = p + seg(qSIG(q)).