[en] 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.

[es] 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, estudiamos una versión bicromática de un problema clásico de geometría combinatoria: Dado un conjunto de puntos en ¿¿ el plano, existen dos puntos tal que todos los círculos que los tienen en su frontera contienen en su interior al menos ¿¿(1 ¿ 1/¿2) ¿ ¿¿(¿¿) otros puntos del conjunto. Este problema combinatorio está fuertemente ligado a los diagramas de Voronoi de orden superior del conjunto de puntos. 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.