Proverbio criollo

El pez confía en el agua, y en agua se cuece.

Aparcamientos caducados

Según leo en el Diario de Sevilla, si avisas a la policía porque alguien ha aparcado delante de tu garaje debidamente señalizado (por lo que has pagado un dinerito además), ellos irán, pero a decirte que no pueden hacer nada, que tu placa de vado está anticuada y que para el caso vale lo mismo poner un póster del Fary (pero del insigne y polifacético cantante de tonillas español).

Al parecer en 2005 se aprobó una ordenanza de tráfico que homogeneizaba las placas de vado en toda España, pero en Sevilla el Ayuntamiento aún no ha sustituido ni una sola de las antiguas, que hoy en día carecen de validez legal.

Maratón

Como (casi) todo el mundo, conocía leyenda que da origen a la maratón: tras vencer al ejército persa en la batalla de Maratón (490 a.C.), un soldado griego recorre los 42 kilómetros que separan este lugar de Atenas. Desfallecido, al llegar a la ciudad sólo le queda aliento para anunciar la victoria antes de morir. Sin embargo nunca me había parado a pensar la razón de este sacrificio. Al fin y al cabo habían ganado la batalla, ¿qué más daba que la noticia se conociera un poco después?

El motivo lo he conocido recientemente al leer Las grandes batallas de la Historia, editado por el Canal Historia, que me regalaron estas navidades (por cierto, me llama la atención que en ningún lugar del libro viene el nombre de un solo autor). Tras la batalla de Maratón los griegos no pudieron evitar que gran parte del ejército persa embarcara de nuevo en su flota y pusiera rumbo a Atenas, objetivo principal de la invasión. La ciudad había quedado desguarnecida, y si sus habitantes veían llegar a la flota persa sin duda pensarían que habían sido derrotados y se rendirían.

Se imponía pues que las buenas noticias llegaran lo antes posible, incitando a los ciudadanos a resistir en tanto regresaba el ejército victorioso. Y se cumplió el objetivo: todos los hombres, mujeres y niños de Atenas subieron a las murallas para dar la impresión de que se encontraban guarnecidas. Los persas cayeron en el engaño y, no atreviéndose a intentar un ataque con el ejército griego en camino, se retiraron sin llegar a desembarcar.

A pesar de su fama, no está claro que la carrera cuya leyenda dio lugar a la maratón sucediese realmente. No aparece en las fuentes hasta cinco siglos después de la batalla. Los historiadores de la época no la citan, aunque sí hacen referencia a otra gesta atlética: la que llevó a cabo Filípides al recorrer en dos días los 246 kilómetros que separaban Atenas de Esparta para solicitar la ayuda de estos últimos. Durante siglos se pensó que era una exageración del historiador Heródoto, hasta que en 1982 tres militares ingleses hicieron la carrera en treinta y seis horas.

Por último una curiosidad: la distancia de la prueba de maratón es de 42.195 km. Esos 195 metros extra aparecieron por primera vez en los IV Juegos Olímpicos celebrados en Londres en 1908, y se añadieron para que la carrera terminase frente a la tribuna real.

El diagrama de Voronoi (II)

Dentro de las entradas con motivo del Carnaval de Matemáticas os contaba en qué consistía el diagrama de Voronoi. Ahora nos extenderemos un poco con algunas propiedades y algo de historia.

Os recuerdo que, dado un conjunto de puntos S en el plano, su diagrama de Voronoi es la partición del plano en regiones, tal que a cada punto de S le hace corresponder la región formada por aquellos puntos que están más cerca suya que de cualquier otro punto de S.

Sencillo, ¿no? Y al mismo tiempo una herramienta muy potente, ya que almacena gran parte de la información relativa a noción de proximidad entre puntos. Por ejemplo, supongamos que cada generador del diagrama es un detector y queremos atravesar un terreno sin disparar las alarmas, ¿por dónde hemos de ir? Lo más lejos posible de cada detector, claro. Pero con cuidado de que al alejarnos de uno no nos estemos acercando demasiado a otro. ¿Cuáles son los puntos que mantienen una mayor distancia entre detectores? Justamente los que forman las aristas del diagrama.

El diagrama de Voronoi (I)

Una entrada para el Carnaval de Matemáticas que empieza con una cita de Groucho Marx que cobrará sentido al final del artículo.

"Claro que lo entiendo. Incluso un niño de cuatro años podría entenderlo. ¡Que me traigan un niño de cuatro años!."

El diagrama de Voronoi es una de las estructuras clásicas en Geometría Computacional (disciplina encargada de resolver problemas geométricos mediante métodos algorítmicos). Es una estructura al tiempo sencilla y poderosa, que parte de una idea tan natural que ha sido descubierta varias veces a lo largo de la historia. De ahí los distintos nombres con los que ha sido conocido: diagrama de Voronoi, polígonos de Thiessen, regiones de Wigner-Seitz, etc.

 

Georgy Voronoi (1868-1908). Foto tomada de Wikipedia.

Pero, ¿qué es el diagrama de Voronoi? Vamos a ilustrarlo con un ejemplo sencillo: supongamos que tenemos una empresa cuya función es ayudar a nuestros clientes a encontrar los servicios más cercanos a su situación actual. Recibimos unas coordenanas por teléfono, web, aplicación móvil... y, en el menor tiempo posible, tenemos que suministrarle la dirección del restaurante, gasolinera, parking, etc. más cercano. ¿Cómo lo hacemos?

Pensemos en el problema de manera geométrica. Partimos de un conjunto de puntos en el plano correspondientes a una categoría de servicios (por ejemplo, gasolineras). Cada consulta de nuestro cliente podemos interpretarla como un nuevo punto que tenemos que emparejar con el más cercano del conjunto inicial. ¿Cómo lo seleccionamos? Fácil, diremos: mido las distancias a cada una de las gasolineras y me quedo con la más pequeña. 

Respuesta correcta, pero no del todo. Repetimos las condiciones del problema: tenemos que dar la respuesta en el menor tiempo posible. ¿Cuánto tardamos con este procedimiento? Lo que nos lleve medir la distancia a cada una de las gasolineras. No podemos hacerlo en menos tiempo porque, a priori, no podemos dejar de comprobar ninguna de ellas. ¿Significa esto que éste el mejor método entre todos los posibles?