Problems and applications of discrete and computational geometry concerning graphs, polygons, and points in the plane

Resumen

Esta tesis trata sobre varios problemas en el área de la geometría discreta y computacional, relacionados con grafos, polígonos y conjuntos de puntos en el plano. La tesis ha sido realizada mediante el compendio de cuatro artículos publicados en revistas. Tras un capítulo introductorio, el capítulo 2 trata sobre el problema del cálculo del núcleo de un polígono llevado al ámbito de la geometría con orientaciones restringidas. En particular, obtenemos un algoritmo para calcular y mantener el O-núcleo de un polígono conforme el conjunto de orientaciones O rota. Este algoritmo proporciona, además, los ángulos de rotación para los que el área y el perímetro del O-núcleo son máximos. En el capítulo 3 consideramos una versión bicromática de un problema combinatorio planteado por Neumann-Lara y Urrutia. En concreto, demostramos que todo conjunto de n puntos azules y n puntos rojos en el plano contiene un par bicromático de puntos tal que todo círculo que los tenga en su frontera contiene en su interior al menos n(1− √12)−o(n) puntos del conjunto. Este problema está fuertemente ligado al cálculo de los diagramas de Voronoi de orden superior del conjunto de puntos, pues las aristas de estos diagramas contienen precisamente todos los centros de los círculos que pasan por dos puntos del conjunto. Por ello, nuestra línea de trabajo actual en este problema consiste en explorar esta conexión realizando un estudio detallado de las propiedades de los diagramas de Voronoi de orden superior. En los capítulos 4 y 5, planteamos dos aplicaciones de la teoría de grafos al análisis sensorial y al control del tráfico aéreo, respectivamente. En el primer caso, proponemos un método que utiliza técnicas geométricas para analizar las opiniones de los consumidores recogidas con mapeo proyectivo. En el segundo, utilizamos la técnica del espectro-coloreado de grafos para plantear un modelo del tráfico aéreo que pretende optimizar el consumo de combustible de los aviones al mismo tiempo que se evitan colisiones entre ellos.