---
tags: geometry, rotating-calipers, polygons
---

# Rotating calipers
Esta técnica es el equivalente a two pointers en geometría. Los problemas a resolver son:
- Par de puntos más lejanos
- Ancho de un polígono
- Smallest enclosing rectangle

## Par de puntos más lejanos ([problema 1](https://www.spoj.com/problems/TFOSS/), [problema 2](https://open.kattis.com/problems/roberthood))
Tenemos un conjunto $S$ de puntos y queremos hallar los dos puntos en $S$ cuya distancia sea máxima ($2 \leq |S| \leq 10^5$). A dicha distancia también se le conoce como el *diámetro* de $S$.

Ejemplo:

Vemos que todos los candidatos a ser los pares más lejanos de puntos siempre se encontrarán en el Convex Hull:


Entonces, el primer paso es asignar $S \gets ConvexHull(S)$. Es muy importante que $S$ en este punto sea estrictamente convexo, es decir, con todos sus ángulos menores a 180°.

Luego, vamos a tener dos punteros $i,j$ dando vueltas en sentido antihorario en el polígono. El primer puntero representará a la línea $\overrightarrow{S_i S_{i+1}}$ y el segundo a la línea $\overrightarrow{S_j S_{j+1}}$. Los vamos a ir moviendo de la siguiente forma:
1. Sea $i \gets 0$, $j \gets 1$ y $ans \gets 0$.
2. Si $i = n$ ya acabamos y la respuesta es $ans$. Si no, vamos al paso 3.
3. Mientras $\overrightarrow{S_i S_{i+1}} \times \overrightarrow{S_j S_{j+1}} > 0$, vamos a avanzar $j$, es decir, $j \gets j+1$. Esto es equivalente a mover el puntero $j$ tal que esté "opuesto" a la arista formada por el puntero $i$.
4. El par de puntos $(S_i, S_j)$ y $(S_{i+1}, S_j)$ son candidatos a ser el par de puntos más lejanos. Basta con checar el par $(S_i, S_j)$, por lo tanto, $ans \gets \max(ans, \lVert S_i - S_j \rVert)$.
5. Avanzamos el puntero $i$, es decir, $i \gets i+1$, y volvemos al paso 2.

En total, la complejidad es $O(n \log n)$, ya que el Convex Hull se ejecuta en $O(n \log n)$ y vemos que el puntero $i$ le da exactamente una vuelta al polígono y $j$ le da a lo más dos vueltas, por lo que este paso siempre se ejecuta en $O(n)$.

:::spoiler **Ejemplo paso a paso**
----------------------------------------------------------------
Con los puntos anteriores, simulemos el algoritmo ya después de haber calculado el Convex Hull. Sean $S_0=A$, $S_1=E$, $S_2=J$, $S_3=L$, $S_4=K$, $S_5=F$ y $S_6=B$. Entonces:
- Comenzamos con $\color{blue}{i=0}$ y $\color{green}{j=1}$:
- El puntero $\color{green}{j}$ lo movemos hasta $\color{green}{j=4}$, es decir, en el punto $K$. Aquí el producto cruz ya se hace negativo:
- Aquí los candidatos a puntos más lejanos son $(A,K)$. Ahora incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=1}$:
- El puntero $\color{green}{j}$ lo movemos hasta $\color{green}{j=6}$, es decir, en el punto $B$. Aquí el producto cruz ya se hace negativo:
- Aquí los candidatos a puntos más lejanos son $(E,B)$. Incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=2}$:
- En este paso ya no fue necesario mover $\color{green}{j}$, pues el producto cruz sigue siendo negativo. Por lo tanto, los candidatos a puntos más lejanos son ahora $(J,B)$. Luego, incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=3}$:
- El puntero $\color{green}{j}$ lo movemos a $\color{green}{j=0}$ (ya dio una vuelta completa) donde el producto cruz ya se hace negativo y tenemos que:
- Aquí los candidatos a par de puntos más lejanos son $(L,A)$. Luego, incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=4}$:
- Incrementamos $\color{green}{j}$ hasta $\color{green}{j=1}$ donde el producto cruz se hace negativo, y tenemos que:
- Los candidatos a puntos más lejanos son $(K,E)$. Luego, incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=5}$:
- En este paso ya no fue necesario mover $\color{green}{j}$, pues el producto cruz sigue siendo negativo. Entonces, los candidatos a puntos más lejanos son $(F,E)$. Luego, incrementamos $\color{blue}{i}$ y queda $\color{blue}{i=6}$:
- Incrementamos $\color{green}{j}$ hasta $\color{green}{j=3}$, donde el producto punto es negativo de nuevo:
- Aquí los candidatos a pares de puntos más lejanos son $(B,L)$.
- Finalmente, como $\color{blue}{i}$ ya dio la vuelta completa, hemos terminado. Resumiendo, los pares candidatos a puntos más lejanos fueron: $(A,K)$, $(E,B)$, $(J,B)$, $(L,A)$, $(K,E)$, $(F,E)$ y $(B,L)$.

----------------------------------------------------------------
:::

## [Ancho de un polígono](https://vjudge.net/problem/UVA-1111)

Sea $S$ un polígono simple. Queremos deslizarlo entre dos rectas paralelas, es decir, que todo el polígono esté contenido en las rectas. El problema es hallar la mínima distancia entre ambas rectas, a la cual le llamaremos el *ancho* del polígono $S$.

Vemos que si $S$ no es convexo, al calcular su Convex Hull su ancho no cambia, pero el algoritmo que veremos solo funciona si $S$ es convexo, por lo tanto, el primer paso es asignar $S \gets ConvexHull(S)$.

En la solución óptima, al menos una de las dos líneas coincide con una arista del polígono, lo que reduce nuestro espacio de búsqueda. Entonces, una primer solución es iterar por cada arista y hacer que la segunda línea paralela pase por el vértice más lejano a esta arista; al final nos quedamos con la mínima distancia. Esta solución funciona en $O(n^2)$, veamos cómo mejorarla.

Del problema anterior vemos que ambos punteros siempre representan las líneas que son las prolongaciones de cada arista. Podemos fijar a $\color{blue}{i}$ como la primer línea $\overrightarrow{S_i S_{i+1}}$; mientras que $\color{green}{j}$ será el punto más alejado de ella, es decir, $S_j$. Entonces el algoritmo es casi idéntico al anterior, solo que ahora calcularemos la distancia perpendicular entre la línea $\overrightarrow{S_i S_{i+1}}$ y el punto $S_j$ cada que $\overrightarrow{S_i S_{i+1}} \times \overrightarrow{S_j S_{j+1}} < 0$. Al final nos quedamos con la mínima de todas estas distancias.

Al final, la complejidad mejoró a $O(n \log n)$.

:::spoiler **Ejemplo paso a paso**
----------------------------------------------------------------

Consideremos el siguiente polígono $P$ que ya es convexo:

- Comenzamos con $\color{blue}{i=0}$ y $\color{green}{j=1}$:

- Movemos $\color{green}{j}$ hasta que $\color{green}{j=3}$, pues aquí $\overrightarrow{P_0 P_1} \times \overrightarrow{P_3 P_4} < 0$. El candidato a ancho del polígono es entonces (longitud del segmento en rojo):

- Avanzamos $\color{blue}{i}$ y queda $\color{blue}{i=1}$:

- Movemos $\color{green}{j}$ hasta que $\color{green}{j=4}$, donde $\overrightarrow{P_1 P_2} \times \overrightarrow{P_4 P_5} < 0$. Ahora el candidato a ancho del polígono es:

- Avanzamos $\color{blue}{i}$ y queda $\color{blue}{i=2}$:

- Movemos $\color{green}{j}$ hasta que $\color{green}{j=0}$ (ya dio una vuelta completa), donde $\overrightarrow{P_2 P_3} \times \overrightarrow{P_0 P_1} < 0$. Ahora el candidato a ancho del polígono es:

- Avanzamos $\color{blue}{i}$ y queda $\color{blue}{i=3}$:

- Movemos $\color{green}{j}$ hasta que $\color{green}{j=1}$, donde $\overrightarrow{P_3 P_4} \times \overrightarrow{P_1 P_2} < 0$. Ahora el candidato a ancho del polígono es:

- Avanzamos $\color{blue}{i}$ y queda $\color{blue}{i=4}$:

- Movemos $\color{green}{j}$ hasta que $\color{green}{j=2}$, donde $\overrightarrow{P_4 P_5} \times \overrightarrow{P_2 P_3} < 0$. Ahora el candidato a ancho del polígono es:

- Avanzamos $\color{blue}{i}$ y queda $\color{blue}{i=5}$:

- No tuvimos que mover $\color{green}{j}$, pues $\overrightarrow{P_5 P_0} \times \overrightarrow{P_2 P_3} < 0$. Ahora el candidato a ancho del polígono es:

- En este punto ya terminamos el algoritmo, pues $\color{blue}{i}$ ya dio una vuelta completa.

----------------------------------------------------------------
:::

[**Ejemplo paso a paso interactivo**](https://www.geogebra.org/classic/szvkqs8f)

## Smallest enclosing rectangle ([problema 1](https://open.kattis.com/problems/fenceortho), [problema 2](https://codeforces.com/gym/100633/problem/E))
Sea $S$ un conjunto de puntos. Queremos hallar el rectángulo de área mínima que encierre a todos los puntos de $S$, cuyos lados no necesariamente estarán alineados a los ejes.

De nuevo, basta con que el rectángulo encierre al Convex Hull de $S$, pues los puntos que no pertenezcan estarán de forma automática dentro del rectángulo. Entonces el primer paso es $S \gets ConvexHull(S)$.

El siguiente paso es tener ahora 4 punteros que girarán de forma simultánea en sentido antihorario, donde cada uno representará a un lado del rectángulo, a los que llamaremos $\color{blue}{i}$, $\color{green}{j}$, $\color{orange}{k}$, $l$:
- $\color{blue}{i}$ representará a la línea $\overrightarrow{S_i S_{i+1}}$ sobre la cuál vamos a recargar el primer lado del rectángulo.
- $\color{green}{j}$ representará al segundo lado del rectángulo tal que está a la derecha del primero: trazaremos la línea perpendicular a $\overrightarrow{S_i S_{i+1}}$ que pasa por $S_j$ tal que no intersecte al polígono en su interior, y sobre ella recargaremos el segundo lado del rectángulo. Es decir, si vamos caminando sobre la dirección de $\overrightarrow{S_i S_{i+1}}$, tendremos que girar 90° a la izquierda para encontrarnos con esta línea.
- $\color{orange}{k}$ representará al tercer lado del rectángulo que es el opuesto al primero: $S_k$ será el punto más lejano a la línea $\overrightarrow{S_i S_{i+1}}$ y vamos a recargar este tercer lado sobre la recta paralela a la línea $\overrightarrow{S_i S_{i+1}}$ que pasa por $S_k$.
- $l$ representará al cuarto lado del rectángulo tal que está a la izquierda del primero: trazaremos la línea perpendicular a $\overrightarrow{S_i S_{i+1}}$ que pasa por $S_l$ tal que no intersecte al polígono en su interior, y sobre ella recargaremos el cuarto lado del rectángulo. Es decir, si vamos caminando sobre la dirección contraria de $\overrightarrow{S_i S_{i+1}}$, tendremos que girar 90° a la derecha para encontrarnos con esta línea.

Sea $ang(\vec{u}, \vec{v}) \in [0, 2 \pi)$ el ángulo que hay que girar siempre en sentido antihorario comenzando en $\vec{u}$ para terminar en $\vec{v}$ si ambos tienen el mismo origen. Tenemos que:
$$
ang(\vec{u}, \vec{v}) = \begin{cases}
\arccos \left( \dfrac{\vec{u} \cdot \vec{v}}{\lVert \vec{u} \rVert \lVert \vec{v} \rVert} \right) &\mbox{si $\vec{u} \times \vec{v} \geq 0$} \\
2\pi - \arccos \left( \dfrac{\vec{u} \cdot \vec{v}}{\lVert \vec{u} \rVert \lVert \vec{v} \rVert} \right) &\mbox{si $\vec{u} \times \vec{v} < 0$}
\end{cases}
$$

Notamos que si $\vec{u}$ es fijo y vamos rotando a $\vec{v}$ en sentido antihorario comenzando con la dirección y sentido de $\vec{u}$, $ang(\vec{u}, \vec{v})$ será monótamente creciente hasta haberle dado la vuelta completa.

Para siempre lograr la condición de que las líneas que representan a cada lado no intersecten al polígono en su interior y que se cumpla la condición de que el rectángulo encierre a todos los puntos, vamos a hacer lo siguiente, teniendo fija la arista $\overrightarrow{S_i S_{i+1}}$:
- Para hallar $j$ vamos a avanzarlo mientras $ang \left(\overrightarrow{S_i S_{i+1}}, \overrightarrow{S_j S_{j+1}} \right) < \frac{\pi}{2}$. Al hacer esto, $S_j$ estará lo más a la derecha posible, pues para llegar de $\overrightarrow{S_i S_{i+1}}$ a $\overrightarrow{S_j S_{j+1}}$ habremos dado al menos 1/4 de vuelta, lo cual hace viable pasar una línea perpendicular por ahí para el segundo lado. La condición equivalente sin usar funciones trigonométricas es $\overrightarrow{S_i S_{i+1}} \cdot \overrightarrow{S_j S_{j+1}} > 0$.
- Para hallar $k$ es igual que como en los otros dos algoritmos, pues es el punto más lejano a la arista $\overrightarrow{S_i S_{i+1}}$, lo cual lo hace viable para pasar una línea paralela por ahí para el tercer lado. Esto se cumplirá cuando para llegar de $\overrightarrow{S_i S_{i+1}}$ a $\overrightarrow{S_k S_{k+1}}$ hayamos dado al menos 1/2 de vuelta. Por lo tanto, vamos a avanzar $k$ mientras $ang\left(\overrightarrow{S_i S_{i+1}}, \overrightarrow{S_k S_{k+1}} \right) < \pi$. La condición equivalente es $\overrightarrow{S_i S_{i+1}} \times \overrightarrow{S_k S_{k+1}} > 0$.
- Para hallar $l$ vamos a avanzarlo mientras $ang \left(\overrightarrow{S_i S_{i+1}}, \overrightarrow{S_l S_{l+1}} \right) < \frac{3\pi}{2}$, es decir, para llegar de la arista $\overrightarrow{S_i S_{i+1}}$ a $\overrightarrow{S_l S_{l+1}}$ hay que girar al menos 3/4 de vuelta para garantizar que esté lo más a la izquierda posible, lo cual hace viable pasar una línea perpendicular por ahí para el cuarto lado. La condición equivalente es $\overrightarrow{S_i S_{i+1}} \cdot \overrightarrow{S_l S_{l+1}} < 0$.

Notemos que siempre que $(S_i, S_k)$ y $(S_j, S_l)$ sean pares de puntos opuestos en el polígono, ya tendremos un candidato a rectángulo mínimo, el cuál está dado por:
- Sea $\vec{u} = \overrightarrow{S_i S_{i+1}}$ el vector de dirección de la primer línea del primer lado, a la que llamaremos $\vec{l_1}$. Sabemos que pasa por $S_i$, por lo tanto la podemos parametrizar como $\vec{l_1} = S_i + t\vec{u}$.
- Sea $\vec{l_2}$ la línea del segundo lado y sea $\vec{v}=\vec{u}^{\perp}$ el vector perpendicular a $\vec{u}$ girado a la izquierda 90° grados. Sabemos que $\vec{l_2}$ para por $S_j$ y su dirección está dada por $\vec{v}$, por lo tanto, $\vec{l_2} = S_j + t\vec{v}$.
- Sea $\vec{l_3}$ la línea del tercer lado. Sabemos que su dirección es paralela a $\vec{u}$ pero en sentido contrario y pasa por $S_k$, por lo tanto, $\vec{l_3} = S_k - t\vec{u}$.
- Sea $\vec{l_4}$ la línea del cuarto lado. Sabemos que su dirección es paralela a $\vec{v}$ pero en sentido contrario y pasa por $S_l$, por lo tanto, $\vec{l_4} = S_l - t\vec{v}$.
- Sean $A,B,C,D$ los vértices del rectángulo en sentido antihorario, por lo tanto $A = \vec{l_1} \cap \vec{l_2}$, $B = \vec{l_2} \cap \vec{l_3}$, $C = \vec{l_3} \cap \vec{l_4}$ y $D = \vec{l_4} \cap \vec{l_1}$.
- Pero si solo estamos interesados en el ancho $w$ y la altura $h$ del rectángulo los podemos calcular de forma más simple: $h$ es la distancia perpendicular entre $S_k$ y $\vec{l_1}$, y $w$ es la distancia perpendicular entre $S_l$ y $\vec{l_2}$.

Entonces, el algoritmo queda como:

1. Sea $i \gets 0$, $j \gets 0$, $k \gets 1$, $l \gets 0$, y $ans \gets \infty$.
2. Si $i = n$ ya terminamos y la respuesta es $ans$.
3. Mientras $\overrightarrow{S_i S_{i+1}} \cdot \overrightarrow{S_j S_{j+1}} > 0$ vamos a avanzar $j$, es decir, $j \gets j+1$.
4. Mientras $\overrightarrow{S_i S_{i+1}} \times \overrightarrow{S_k S_{k+1}} > 0$ vamos a avanzar $k$, es decir, $k \gets k+1$.
5. Si $i=0$ le damos el primer valor a $l$, es decir, $l \gets k$.
6. Mientras $\overrightarrow{S_i S_{i+1}} \cdot \overrightarrow{S_l S_{l+1}} < 0$ vamos a avanzar $l$, es decir, $l \gets l+1$.
7. Ya tenemos un candidato a rectángulo mínimo en este punto. Calculamos su área $wh$ y actualizamos la respuesta: $ans \gets \min(ans, wh)$.
8. Avanzamos el puntero $i$, es decir, $i \gets i+1$, y volvemos al paso 2.

Este algoritmo también funciona para hallar el rectángulo con mínimo perímetro, solo que no necesariamente tendremos que el rectángulo con área mínima es el mismo rectángulo con perímetro mínimo.

[**Ejemplo paso a paso interactivo**](https://www.geogebra.org/classic/qtn5xj4q)