Dejemos que $$\ell_0= (x_k,y_k)_{0\leq k\leq N}$$ avec $x_0<x_1<\ldots<x_N$ sea el borde inferior del corredor, mantenido fijo en la secuela, y dibujado en rojo en la siguiente figura. El borde superior, dibujado en azul, es congruente con $\ell_0$ y en el momento $t=0$ coincide con $\ell_0$ . En la red $\ell_0$ marcar todo $\wedge$ -Versos rojos, y en el azul $\ell_0$ marcar todo $\vee$ -Vertederos azules. Trasladaremos el borde superior lentamente hacia arriba, de forma que en el momento $t$ tenemos $$\ell_t= (x_k,y_k+t)_{0\leq k\leq N}\quad(0\leq t\leq h)\ .$$
Denota por $\gamma_t$ el camino más corto a través del corredor en el momento $t$ . Cuando $t>0$ es casi cero, entonces $\gamma_t$ pasará por todos los vértices marcados $V_k$ Además $\gamma_0$ tiene un $\wedge$ en todos los vértices rojos y un $\vee$ en todos los vértices azules. Como $t$ está aumentando la $\wedge$ s así como el $\vee$ s se vuelven menos francos, y algunos de ellos incluso se volverán heterosexuales. Cuando se produce un acontecimiento de este tipo $\gamma_t$ se desacoplará de ese vértice $V$ que entonces queda definitivamente fuera de consideración.
Esto ocurre de la siguiente manera: Supongamos que un vértice "activo" $V_k$ tiene al menos un vecino del otro color. Hay varios casos a considerar, pero será suficiente con describir el siguiente caso: En el momento $t$ tenemos un vértice rojo $V_{k-1}=(x_{k-1}, y_{k-1})$ y vértices azules $V_k=(x_k,y_k+t)$ , $V_{k+1}=(x_{k+1},y_{k+1}+t)$ . Desde $V_k$ está activo tenemos $${y_k+t-y_{k-1}\over x_k-x_{k-1}}<{y_{k+1}-y_k\over x_{k+1}-x_k}\ .\tag{1}$$ Cuando $t$ aumenta el lado izquierdo de $(1)$ aumentará, y el lado derecho permanecerá constante, ya que ambos $V_k$ y $V_{k+1}$ son azules. Habrá un cierto valor $\tau_k>t$ cuando se alcanza la igualdad. Este valor $\tau_k$ es una función racional de los datos que aparecen en $(1)$ .
Esto nos lleva al siguiente algoritmo:
Poner $t_0=0$ , $\gamma_0=\ell_0$ .
Repito: Supongamos que $t_n<h$ y $\gamma_n=\gamma_{t_n}$ se han determinado, y todos los vértices $V_k$ , rojo o azul, de $\gamma_n$ están activos. A continuación, busque $j:=\arg\min_k \tau_k$ , poned $t_{n+1}:=\tau_j$ y eliminar $V_j$ de la pila.
Deténgase cuando $t_n\geq h$ .