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

Alejandra Martínez-Moraian

• español

  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.

• English

  This thesis deals with problems and applications of discrete and computational geometry in the plane, concerning polygons, point sets, and graphs. After a first introductory chapter, in Chapter 2 we study a generalization of a famous visibility problem in the framework of O-convexity. Given a set of orientations (angles) O, we say that a curve is O-convex if its intersection with any line parallel to an orientation in O is connected. When O = {0◦, 90◦}, we find ourselves in the case of orthoconvexity, considered of special relevance. The O-kernel of a polygon is the subset of points of the polygon that can be connected to any other point of the polygon with an O-convex curve. In this work we obtain, for O = {0◦} and O = {0◦, 90◦}, an algorithm to compute and maintain the O-kernel of a polygon as the set of orientations O rotates. This algorithm also provides the angles of rotation that maximize the area and perimeter of the O-kernel. In Chapter 3, we consider a bichromatic version of a combinatorial problem posed by Neumann-Lara and Urrutia. Specifically, we prove that every set of n blue and n red points in the plane contains a bichromatic pair of points such that every circle having them on its boundary contains at least n(1 − √12) − o(n) points of the set in its interior. This problem is closely related to obtaining the higher order Voronoi diagrams of the point set. The edges of these diagrams contain, precisely, all the centers of the circles that pass through two points of the set. Therefore, our current line of research on this problem consists on exploring this connection by studying in detail the properties of higher order Voronoi diagrams. In Chapters 4 and 5, we consider two applications of graph theory to sensory analysis and air traffic management, respectively. In the first case, we introduce a new method which combines geometric and statistical techniques to analyze consumer opinions, collected through projective mapping. This method is a variation of the method SensoGraph. It aims to capture the essence of projective mapping by computing the Ecuclidean distances between pairs of samples and normalizing them to the interval [0, 1]. We apply the method to a real-life scenario and compare its performance with the performance of classic methods of sensory analysis over the same data set. In the second case, we use the Spectrum Graph Coloring technique to propose a model for air traffic management that aims to optimize the amount of fuel used by the airplanes, while avoiding collisions between them.