Resumen de Diseño de redes óptimas en la métrica L1
Debido a sus múltiples aplicaciones, el diseño de redes es uno de los problemas más estudiados dentro de la Geometría Computacional. El problema que se plantea es el de concectar una nube de puntos mediante una buena red, donde la calidad de la red se medirá según lo que se requiera de ella. Así, en muchos de estos problemas es interesante encontrar grafos con pocas aristas que aproximen la distancia entre cada pareja de puntos. Estos grafos llamados spanners han sido ampliamente estudiados, principalmente en la métrica euclídea. Sin embargo, puesto que en muchos casos las redes son ortogonales, la métrica que refleja las distancias entre los puntos es la métrica L1.
En este trabajo consideramos el problema de la construcción de spanners en la métrica L1, no sólo adaptando métodos ya conocidos para la métrica euclídea sino diseñando nuevos métodos basados en las propiedades geométricas específicas de esta métrica. Además, hacemos un estudio más detallado para el diseño de redes sin cruces y redes sin ciclos.
