Departamento de Computación

La geometría combinatoria es una rama de las matemáticas que estudia las propiedades combinatorias de objetos discretos como lo son puntos en el plano y segmentos de recta. La teoría de gráficas trabaja con objetos matemáticos llamados gráficas, una gráfica G es una pareja de conjuntos G = (V;E), donde V es un conjunto finito distinto del vacío y E es un subconjunto de parejas de elementos de V. Una gráfica geométrica es un dibujo de una gráfica en el plano, de tal forma que los vértices de la gráfica son puntos en posición general y las aristas son segmentos de recta entre parejas de puntos. En esta tesis tenemos como objetivo el dar un algoritmo que determine si una gráfica geométrica particular, llamada thrackle, se puede dibujar sobre un conjunto de puntos dado. Una thrackle es una gráfica geométrica en la que todos los segmentos de recta tienen un punto en común, cuando la gráfica tiene tantos segmentos como puntos se dice que es máximo. Abordamos el problema mediante la búsqueda de thrackles máximos en algunas familias de puntos, primero realizamos pruebas computaciones mediante la técnica de backtracking, para posteriormente proponer y demostrar la existencia de thrackles máximos en las siguientes familias de puntos: doble círculo, doble cadena convexa, doble cadena zig-zag, doble cadena zig-zag generalizada y conjunto de Horton, así como seis conjuntos de puntos particulares, además dimos la forma explícita de los thrackles para estas familias de puntos.

Abstract

Combinatorial geometry is a branch of mathematics that studies the combinatorial properties of discrete objects such as points in the plane and line segments. Graph theory works with mathematical objects called graphs, a graph G is a pair of sets G = (V;E), where V is a finite set other than empty set and E is a subset of pairs of elements of V. A geometric graph is a drawing of a graph in the plane, in such a way that the vertices of the graph are points in general position and the edges are line segments between pairs of points. In this thesis we aim to give an algorithm that determines whether a particular geometric graph, called thrackle, can be drawn on a given set of points. A thrackle is a geometric graph in which all the line segments have a point in common, when the graph has as many segments as there are points, it is said to be a maximum. We approach he problem by searching for maximum thrackles in some families of points, first we perform computational tests using the backtracking technique, to later propose and demonstrate the existence of maximum thrackles in the following families of points: double circle, convex double chain, double zig-zag chain, generalized double zig-zag chain and Horton set, as well as six particular point sets, we also gave the explicit form of the thrackles for these point families.r the establishment of a shared key and the generation of ephemeral identifiers as countermeasures against possible security threats in this type of technology.