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? 

Humor y matemáticas

Una de las cosas que llama la atención a muchos de mis amigos no-matemáticos es la cantidad de chistes sobre matemáticas que existen (no hay más que hacer una búsqueda, o dos, para darse cuenta). Siempre me ha gustado esa capacidad para reírnos de nosotros mismos que no he encontrado en casi ninguna otra especialidad.

Así, que aprovechando el Carnaval de Matemáticas, he vuelto a reunir algunas de mis viñetas favoritas. Que os divirtáis.

Me la envió Zifra.

 

De xkcd.

No hay lugar para las matemáticas feas

Para sumarme al Carnaval de Matemáticas os traigo un pensamiento de G. H. Hardy:

Los modelos de un matemático, al igual que los de un pintor o un poeta, deben ser hermosos; las ideas, como los colores o las palabras, deben ensamblarse de una forma armoniosa. La belleza es la primera señal, pues en el mundo no hay un lugar permanente para las matemáticas feas.

Hasta aquí bien, pero luego leo que en su libro A Mathematician's Apology Hardy consideraba como matemáticas feas a la matemática aplicada, y eso me escuece un poco más (aunque reconozco que es cuestión de gustos).

La canción húngara del suicidio

Estamos en el restaurante Kispipa de Budapest, en 1933. Encargado de amenizar la comida, como suele ser habitual, se encuentra el pianista autodidacta Rezső Seres. Pero esa noche es distinta; Rezső estrena una composición nueva: Szomorú vasárnap, más conocida como Gloomy Sunday, en la que pone música a un poema del mismo título de su compatriota László Jávor. Al parecer el mismo Jávor había pedido a Seres que pusiera música al poema que relataba una infortunada aventura que había tenido con una mujer casada. 

Los clientes del Kispipa no son conscientes de que están escuchando por primera vez la que será conocida como la canción húngara del suicidio. Según cuenta la leyenda, desde entonces la tristeza de la canción ha hecho que muchos que la escuchaban decidiesen acabar con su vida. El propio Seres muere al arrojarse desde una ventana poco después de su 69 cumpleaños.

Aunque la asociación de la canción al suidicio posiblemente no fuera más que un truco publicitario, la leyenda circuló ampliamente, llegando incluso a que la BBC prohibiera su emisión. Prohibición que se relajó luego permitiendo radiar solo la versión instrumental.

El restaurante Kispipa sigue manteniendo un piano, presidido por un retrato de Rezső Seres. Los clientes pueden solicitar al pianista Gloomy Sunday (aún a riesgo de que se suiciden sin pagar la cuenta).

Restaurante Kispipa en la actualidad. Gracias a Almar por la foto.

Para acabar os dejo con la versión que la popularizó en el mundo, en la voz de Billie Holiday. Bajo vuestro propio riesgo.