Two problems about convex polygons in discrete geometry

Abstract

En este trabajo abordamos dos problemas sobre polígonos convexos, con vértices en un conjunto finito de puntos en el plano, en posición general. En el primer problema, obtenemos el dibujo rectilíneo de la gráfica completa, con vértices en la colección de puntos dada, y colorearemos las aristas de acuerdo a la siguiente regla: para cualesquiera dos aristas, si sus cerraduras son disjuntas, entonces deben tener diferente color. Estudiaremos el número de colores necesarios y suficientes que debe tener cualquier coloración de este tipo. En este trabajo, encontramos el número de colores necesarios y suficientes para colorear las aristas de la gráfica completa, cuando los vértices están en la doble cadena. Cabe mencionar que, este problema estaba resuelto únicamente para cuando la colección de puntos es el conjunto de vértices de un polígono convexo. Probaremos que si coloreamos, de manera óptima, las aristas con extremos en la cadena mayor, y posteriormente, seleccionando cada vértice restante, y coloreando del mismo color sus aristas incidentes, entonces el número de colores empleados es el óptimo. De nuestro resultado, conjeturamos que, para obtener una coloración óptima en cualquier colección de puntos, se procede de manera semejante: colorear, de manera óptima, las aristas con extremos en el polígono convexo más grande, y posteriormente, seleccionando cada vértice para colorear de un solo color todas las aristas incidentes a él. Formalmente, estamos coloreando, de manera óptima, la gráfica de disjuntez GD = (VD, ED), inducida de un conjunto P de puntos en el plano en posición general. Obtenemos a GD de la siguiente manera: tomamos el dibujo rectilíneo D de K|P| = (P, E) y hacemos VD = E, y ED = {ee′ : las cerraduras de e y de e ′ no se intersectan en D}. Que, como mencionamos, tal número cromático sólo es conocido para cuando P es el conjunto de vértices de un polígono convexo. Probamos que la gráfica de disjuntez, en la doble cadena, tiene un número cromático sustancialmente más grande que el que se conoce. En el segundo problema que estudiamos, nos interesa que los polígonos sean vacíos, y no necesariamente buscamos el más grande. Buscamos particionar el cierre convexo del conjunto de puntos dado P con polígonos con vexos, con interiores disjuntos, cuyos vértices estén en P. A este conjunto de polígonos se le llama descomposición convexa. Estamos interesados en descomposiciones convexas de cardinalidad mínima. Por poner un ejemplo, tenemos a las triangulaciones: descomposiciones convexas cuyos elementos, desde luego, son triángulos. El número de elementos en una triangulación es bien conocido. Si pudiéramos encontrar una descomposición convexa cuyos elementos fueran cuadriláteros, su cardinalidad sería la de una triangulación dividida por dos. Pero es fácil encontrar colecciones de puntos que no admiten cuadrilaterizaciones, en las que todos sus elementos sean convexos. Partiremos de una triangulación específica y encontraremos aristas que pueden ser eliminadas para obtener polígonos convexos más grandes, reduciendo la cardinalidad de la descomposición.

In this work we study two problems involving convex polygons with its vertices in a given point set. In the first problem, we obtain a rectilinear drawing of the complete graph and color the edges according to the unique rule: for any given two edges, if their closures are disjoint, then they must have different color. We analyze how to color all the edges using as fewest colors as possible, when the set of vertices is the double chain. We prove that to use the fewest colors, first, we color the edges with its endpoints in the biggest convex chain in an optimal way, and second, we select every remaining point and color all of its incident edges with a new different color. We conjecture that the optimal way of coloring the edges of the complete graph with vertices in any given point set is similar: first obtain the biggest subset of points in convex position (without caring if it is empty or has another elements in its interior) to color all its incident edges in an optimal way, and second, color the remaining edges by coloring with one different color all the edges incident with each of the remaining vertices. Formally, we are studying the chromatic number of the edge disjointness graph of the complete graph, with its vertex set in a given point set. As far as we know, such chromatic number is only known when the point set is the set of vertices of a convex polygon. In the double chain we obtain a number substantially bigger than the previous one. In the second problem, we care if the polygons are empty, and we may not be interested in the biggest one, we are interested in decompose the convex hull using the smallest number of empty interior disjoint convex polygons, with vertices in the given point set. Specifically, we give an upper bound on the number of these polygons. Such set of polygons is called Convex Decomposition. For instance, a triangulation is a convex decomposition in which every element, obviously, is a triangle. The number of triangles obtained is well known. If we could decompose in quadrilaterals, the number of elements, would be the number of triangles divided by two; if we could decompose in pentagons, the number of elements would be the number of triangles divided by three, etcetera. But its easy to find point sets that do not admit a convex decomposition containing only quadrilaterals (and hence only pentagons, or only hexagons, and so on). So we are allowing different polygons. It is known that, in any triangulation always we can find pairs of triangles that can be joined to obtain convex quadrilaterals. We use this idea to obtain bigger convex polygons, such pentagons or hexagons, and get a better upper bound. By the nature of the problems we study in this work, we remark that, all the point sets we consider have no three or more elements on a line.