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

Abstract

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.