Si Euclides hubiese conocido Manhattan...

Si Euclides hubiese conocido Manhattan, no diríamos que la distancia más corta entre dos puntos es la línea recta. Puesto que si  estamos pensando en diseñar una ruta que una dos puntos dentro de la Gran Manzana (o cualquier ciudad), la distancia real no siempre es la medida del segmento que une a esos puntos, puesto que en la mayoría de los casos, ese segmento atravesará algún rascacielos. Y eso no está bonito, no. 

Figura 1

En la Geometría Euclideana, que es la geometría que todos aprendemos desde nuestros primeros años de estudios, la distancia entre dos puntos se mide como la longitud del segmento que los une, o dicho de otra forma, como el módulo del vector que esos dos puntos definen. Esa forma de medir la distancia es conocida como distancia euclídea y es la que usamos cuando medimos usando un metro entre los dos extremos de lo que queremos medir. En realidad, se trata de una consecuencia del Teorema de Pitágoras. Si tenemos dos puntos en el plano de coordenadas (a,b) y (c,d) respectivamente y queremos calcular la distancia euclídea entre ellos, basta con fijarse que la longitud de los catetos del triángulo rectángulo que definen son (c-a) la de uno y (d-b) la del otro.  Entonces, por el Teorema de Pitágoras, sabemos que la distancia euclídea se mide como

 √(c-a)²+(d-b)^2.

Ahí todo está bien y correcto, pero esa no es la única forma de medir la distancia entre dos puntos en el plano. Existe otra distancia, conocida como Distancia de Manhattan o Distancia 
L₁, que mediría la distancia entre los puntos de la Figura 1 como 

 (c-a) + (d-b)

Es decir, la suma de las longitudes de los dos catetos del triángulo rectángulo. O bien, la de cualquier ruta que una al punto (a,b)  con el punto (c,d) a través de segmentos horizontales y verticales, en otras palabras, la longitud de cualquier escalera que suba desde (a,b)  con el punto (c,d) 

En verde, la distancia euclídea, y en rojo, azul y amarillo, la distancia Manhattan. (Imagen  sacada de aquí)

Pues bien, cuando se trata de diseñar rutas de recorrido mínimos en ciudades, tiene más sentido usar esta distancia que la Euclídea, por lo de no atravesar rascacielos que habíamos dicho. Es más, puesto que todas las 'escaleras' tienen la misma longitud, nos permite elegir entre distintas opciones, en función de semáforos, zonas de dudosas seguridad, etc...

Evidentemente, no todas las ciudades, ni siquiera Nueva York, están distribuidas como una cuadrícula, pero se considera para según qué problemas de dieños de rutas este tipo de distancia. Y también, cómo no, en el diseño de circuitos ortogonales en los que predominan la conexiones en vertical y horizontal, o en el de un plano de metro.

Otra cosa que no diríamos si pensáramos con la distancia de Manhattan es “No había nadie en 10 Km a la redonda” Porque cuando utilizamos esta expresión, estamos intrínsecamente midiendo con la distancia euclídea. Con esta distancia, la que usamos habitualmente en el día a día, los puntos que están a menos distancia de 10 Km de nosotros, son aquellos que están contenidos en un círculo alrededor nuestra de radio 10 Km.

Pero si pensáramos con la distancia de Manhattan, no sería un círculo, sino ¡un rombo!

Todos los puntos de la frontera del círculo de la izquierda están a la misma distancia euclídea del origen de coordenadas, y todos los puntos de la frontera del rombo de la izquierda están a la misma distancia L₁ del origen de coordenas, como se explica en la siguiente figura:

El punto verde y el punto rojo están a la misma distancia del punto azul (nótese que el ángulo formado por el rombo y el eje en el punto verde es de 45º y, por lo tanto, la longitud de los dos catetos del triángulo rectángulo formado es la misma, está representada con a en la Figura) Y en general, cualquier punto de la frontera del rombo está a la misma distancia del origen (punto azul).

Ahora vamos a ver, que  dependiendo de la distancia elegida, el punto más cercano a uno dado puede ser distinto, lo que sería de utilidad conocer a la hora de diseñar rutas de longitud mínima, por ejemplo, para empresas de distribución, mensajería...

Si usamos la euclídea (la usual) el punto rojo está más cerca del origen (en azul) mientras que si usamos la de Manhattan el origen esá más cerca del punto verde. 

Pues bien, ahora que ya conocemos la distancia Manhattan, os formulo una pregunta. Si tenemos dos puntos sobre el plano, P y Q, los puntos que están a la mitad de camino entre P y Q, a la misma distancia de ambos, definen una recta que conocemos, como mediatriz.

¿Y si usamos la distancia L₁,? ¿Qué aspecto tiene la mediatriz entre P y Q? 

Vamos a verlo. Construimos el rectángulo definido por P y Q

Como la distancia de P a Q es (a+b), los puntos sobre la mediatriz PQ, son los que están a distancia (a+b)/2 de cualquiera de ellos, por ejemplo, R y S

Pero también estarán en la mediatriz PQ todos los puntos del segmento RS, vamos a verlo en la figura siguiente con el punto T

En la figura se ve que d(P,S)=d(P,T)= (a+b)/2 (d(P,S) es la forma de escribir "distancia de P a S") y que la d(Q,R)=d(Q,T)=(a+b)/2 y, por lo tanto, T está en la meditariz PQ. Igualmente, se podría razonar con cualquier punto del segmento RS.

Pues bien, para terminar la mediatriz, sólo hay que añadir las demirrectas verticales que parten, respectivamente, de R y de S, 

obteniendo la siguiente poligonal que divide al plano en dos semiplanos, los que están más cerca de P que de Q y viceversa.

No me negaréis que quedarían más monas las lindes de las parcelas con este tipo de mediatrices, ¿no?.

Eso sí, puede que la distancia Manhattan sea más práctica y refleje mejor la realidad en el diseño y optimización de rutas de distribución, pero mi experiencia como madre me permite asegurar que cuando somos niños es la distancia eulcídea la que 'traemos' instalada: "De aquí para acá, mío, de aquí para allá, tuyo"

PS: Cuando explico esta distancia a mis estudiantes no puedo resistir la tentación de llamarla Distancia del Ensanche, y es que Barcelona es mi debilidad.

Con esta entrada participo en la Edición 2.6 del Carnaval de Matemáticas que este mes se aloja en La vaca esférica

Vota Mati: We can do it!

Hoy han salido las primeras clasificaciones parciales de los Premios Bitácoras 2011 y entre ellas, las de Mejor Blog de Educación. 

En ésta, en un maravilloso 2º puesto está nuestra Mati y sus Mateaventuras. 

Sí, Mati es la pelirroja con gafas que aparece en el margen izquierdo de este blog y que cada 15 días, nos trae alguna nueva aventura desde el Pequeño Libro de Notas 

La idea de estas entregas es la de acercar el maravilloso mundo de las Matemáticas a todos, contando de forma cercana, o, al menos, eso intentamos,, tanto curiosidades clásicas y muy conocidas, como otras más nuevas dentro de la Matemática Discreta que es el campo donde yo me "muevo" 

Mati no está pensada sólo para niños, también para educadores, familias y, en definitiva, para cualquier persona curiosa que quiera divertirse con las mates. 

Mati nace del encuentro, por culpa de @LaReciclante , entre una artista catalana, Raquel Garcia Ulldemolins y una matemática andaluza, yo misma. Parece el principio de un chiste, pero es el principio de una historia de trabajo e ilusión que, cada quince días, se convertirá en un nuevo capítulo. 

Así, que si te gusta nuestro proyecto y quieres ayudarnos a conseguir un premio en los Bitácoras 2011, te invitamos a votarnos en los mismos. Es muy fácil, son 2 minutos. Te cuento a continuación cómo:

Se entra en http://bitacoras.com/premios11

En la esquina superior derecha, te registras como nuevo usuario, donde pone Entrar (si tienes cuenta de Facebook o de Twitter, pincha sobre el icono correspondiente y sólo tendrás que elegir un nombre de usuario en Bitácoras, ellos importan tus datos desde Facebook o Twitter)

 Seguidamente rellena los campos con tus datos y creas el usuario

Luego vuelves a http://bitacoras.com/premios11 y seleccionas Votar, en el menú azul claro debajo del menú azul más oscuro de la cabecera de la página

Busca la categoría Mejor Blog de Educación y escribes la dirección de Mati. La dirección de Mati es http://pequenoldn.librodenotas.com/matiaventuras

 Finalmente, realiza la confirmación de seguridad y pulsa VOTAR

Muchas gracias a todos los que nos habéis votado y a los que no, ¿a qué estáis esperando? ¿eh? 

Mind the map

La historia del mapa del metro de Londres es bastante conocida entre los que trabajan o alguna vez hemos trabajado en Teoría de Grafos, o más concretamente, en Inmerión de Grafos (Graph Drawing). ¿Por qué? Pues básicamente, porque nos permite explicar de forma sencilla y casi anecdótica la importancia de la representación de un grafo.

De forma coloquial y sencilla, un grafo no es más que un conjunto de elementos, a los que llamaremos vértices, que se unen entre ellos, por parejas, no necesariamente todos, definiendo lo que llamamos aristas del grafo. Para muestra, un grafo:

Los vértices serán los elementos del conjunto {1, 2, 3, 4} y las aristas {(1,2),(1,3), (1,4), (2,3), (2,4), (3,4)} (vamos, lo que son cuatro puntos, todos unidos con todos).

Ése es el grafo. De hecho, es un grafo conocido como K₄ y una posible representación (dibujo) del mismo  sería ésta (Figura 1)

Figura 1

O sea, que para que nos entendamos, una representación   es un dibujo del grafo. Pero ésa no es la única posible representación  de K₄ también podríamos dar otra, como se puede ver en la Figura 2

Figura 2

Y si te preguntas para qué buscar otra representación distinta, pues, por ejemplo, porque la de la Figura 2 no tiene cruces entre sus aristas, es una representación plana como decimos los de Grafos. Y las representaciones planas son mejores cuando se diseñan, por ejemplo, circuitos.

Ahora, a ver, si tenemos K₅ (5 vértices, todos unidos con todos) ¿es posible dar otra representación distinta sin cruces entre sus aristas? O como decimos en Teoría de Grafos, ¿es posible dar una inmersión plana de K₅? Os dejo unos minutos para que lo intentéis.

Una inmersión de K₅

Venga, no os agobiéis, no es posible. De hecho es uno de los teoremas más famosos de la Teoría de Grafos, el Teorema de Kuratowski

Hasta aquí espero haberos convencidos de la importancia del dibujo de un grafo. Para un mismo conjunto de vértices y una misma lista de conexiones entre ellos, puede haber trazados con o sin cruces entre las líneas. Pero vamos a ver otro ejemplo antes de hablar del mapa del metro de Londres.

En la siguiente ilustración, tenemos 4 grafos.

Si nos fijamos bien, en el grafo I₁, se ve fácilmente que este grafo es Hamiltoniano, hay un camino que pasa por todos los vértices y vuelve al de origen, sin repetir vértices. El grafo I₂ es fácil ver que es un grafo regular, es decir, de todos los vértices sale el mismo número de aristas. En cuanto al grafo I_3, se puede intuir que es un grafo plano, que se puede dibujar sin cruces entre aristas. Y, por último, si miramos el grafo I4, se ve claramente que es bipartito, es decir, se pueden colorear los vértices usando sólo 2 colores, de forma que nunca se conecten vértices del mismo color. 

Pues bien, los 4 son el mismo grafo, son 4 dibujos distintos del  mismo grafo.

En definitiva, depende del dibujo que hagamos de nuestro grafo, de la representación que elijamos, podemos destacar, y por lo tanto aprovechar, una característica u otra  del grafo. Por lo tanto, parece que merece la pena detenerse un poco a la  hora de dibujar un grafo,

Nos vamos a Londres. ¡Venga!

Londres, Febrero de 2001

                                   

Los primeros mapas del metro de Londres eran geográficos, básicamente, consistían en dibujar sobre un plano de la ciudad los recorridos de las distintas líneas.

Mapa del metro de Londres en 1908

Fue Harry Beck, ingeniero electrónico empleado en el metro de Londres, el primero que se percató de que al usuario no le interesaba conocer el recorrido del metro bajo tierra, sino simplemente, conocer la posición relativa de las líneas y estaciones para realizar los trasbordos que necesitase. 

Harry Beck

Se le ocurrió entonces, en 1931, que en realidad, más que un diseño geográfico, lo que resultaría útil sería un diseño topológico, con menos curvas y direcciones en las líneas, y, de broma, hizo su primer diseño basado en los utilizados en circuitos eléctricos. Aún un poco reticentes, lanzaron la idea de Beck entre los usuarios y fue aceptada con entusiasmo por los usuarios del metro.

Primer mapa de Beck de 1933

Y hasta hoy, esa idea topológica del mapa de Beck, es la más utilizada en el mundo para este tipo de  planos, incluso hasta en nuestro metro de Sevilla, aunque aquí, sinceramente, aún podríamos permitirnos el geográfico.

Metro de Sevilla

Éste es otro ejemplo más de la importancia del dibujo de un grafo, puesto que podemos entender las estaciones como vértices y las líneas como aristas. De hecho, Beck, a lo largo de su trayectoria, introdujo diversos cambios a su diseño original en pos de conseguir mayor claridad en el plano. 

En 1936, entre otros cambios, eliminó curvas y sólo permitió ángulos de 45º y 90º 

Mapa de 1936

En 1940, le pidieron, entre otros detalles, que incorporase ángulos de 60º también, idea que se desechó por enturbiar la claridad del plano. 

Mapa en 1941

Se puede consultar aquí la evolución de los mapas de del metro de Londres y observar qué tipo de modificaciones iban apareciendo siempre para mejorar la usabilidad de los mismos. 

Plano de 2011

Pero si  leemos esa evolución, nos damos cuenta de que no sólo se trata de dar un trazado topológicamente correcto y sencillo para el usuario, sino que se topan con otro problema: las etiquetas. Deben tener suficiente tamaño para que se puedan leer, pero lo justo para que no se "amontonen" en el mapa y para que el tamaño del plano del metro no sea del tamaño de una catálogo de Worten. 


Y ese problema, el problema del etiquetado de mapas, map labeling problem, no acerca un poco a algo que me gusta bastante, la Geometría Computacional. 


Lo que me llamó la atención la primera que oí hablar de este tipo de problemas, como muchos de los abordados por la Geometría Computacional, es la sencillez de su planteamiento y la increíble dificultad de dar una buena solución.


¿De qué se trata? Pues de que tenemos que poner etiquetas en un mapa a: puntos, líneas (curvas o poligonales) y regiones. Hay que hacerlo de forma legible, sin ambigüedades y sin solapamiento de las etiquetas. 

Etiquetas para puntos

Hay que cumplir además ciertas reglas, más o menos, aceptadas por todos. 


En el etiquetado de puntos, por ejemplo: se prefiere que la etiqueta esté a la derecha (no a la izquierda), que esté arriba (no por debajo)...


En el etiquetado de líneas poligonales o curvas, las etiquetas deben conservar una distancia mínima, no debe intersectar a la línea etiquetada, con poca curvatura, pocos puntos de inflexión, lo más horizontal posible... 


En el etiquetado de regiones, no debe cruzar la frontera de la región, debe quedar claro cuál es la región completa etiquetada, que no entre en conflicto con etiquetas de puntos o líneas...etc.

Pues bien, dada la complejidad y el hecho de que los problemas de etiquetado de mapas no se reducen sólo al ámbito de transportes públicos, éstos han dado lugar a muchísmos trabajos de investigación y a una larga lista de algoritmos de aproximación para tratar de resolverlos. 


Desgraciadamente, no existen  buenos algoritmos que resuelvan el problema computacional, es por ello que aún hoy en día, el etiquetado de los mapas se hacen a mano. Un experto puede poner entre 20 y 30 etiquetas en un mapa por hora.


Así que en contra de lo que algunos piensan, no es tan fácil colocar etiquetas.... lo dejamos por aquí. Eso sí, colorearlos, sabemos que sólo con cuatro colores.


Si te interesa el tema, te recomiendo un paseo por esta página de Alex Wolff o echarle, por ejemplo un vistazo a este otro trabajo. 

Este mapa, de 2003, está en el London Transport Museum

Con esta entrada participo en la Edición 2.6 del Carnaval de Matemáticas que este mes se aloja en La vaca esférica

Credenciales

Ayer decidí bajar a la playa de las Cortinas, a través del garito Caños Piratas.

Un chico lleno de tatuajes y piercings con el torso descubierto barría la escalera.

―Buenos días, ¿puedo bajar por aquí hasta la playa?

―Claro, 'mujé', ¿'po' no 'va' a 'podé'?, chiquilla... Ahora, pero una cosa te voy a 'decí': ¡mira! ―se baja el pakistaní de rayas y me enseña su culo, intensamente bronceado (y turgente, por cierto) ―Nada de tonterías, ¿eh?, que se está convirtiendo esto en una playa normal con tanto 'bañadó'... coño...


―Tranquilo, confía en mí.


Le enseñé el mío.