Métodos computacionales en geometría discreta

Abstract

The present document has the purpose of showing the work I have done about three Discrete Geometry problems during my PhD studies. The approach used has the addition of using computational tools. These tools appear in some ways such as the assistance in the study of those problems, making a computationally assisted proof, search of examples, and algorithms design. In the same way, there are pure math proofs of results in the presented subjects. About the first problem, in this work, an approach to studying the problem of deciding under which conditions we can tessellate a polygon with congruent pieces is shown. In the same chapter, there is a computationally assisted proof of the fact that we could not tessellate squares or rectangles with an odd amount n ≤ 9 and n ≤ 7 of congruent pieces unless those are rectangles, respectively. Moreover, there is a list with all tessellations of squares with equiangular pieces for n ≤ 5. In the next chapter, some progress is presented about the problem of deciding the minimum dimension in which a set of points can be realized such that, a prescribed order over their distances is satisfied. The first one is the observation that a type of order, which has been presented in another work as unrealizable in a dimension is realizable in that one. For this, a general construction of points is shown. The second one is the proof of the fact that, for bipartite orders with n < m, the minimum dimension those orders can be realized is n. To finish, some computational results are presented. The last chapter concerns problems on measures and point sets partitions in Rd.

El presente documento tiene como propósito mostrar el trabajo realizado sobre tres problemas de Geometría Discreta en los cuales he trabajado durante mis estudios de doctorado. El enfoque utilizado cuenta con el añadido del uso de herramientas computacionales. Las mismas aparecen en varios aspectos como los son: la asistencia en el estudio de los problemas, el diseño de una demostración asistida por computadora, la búsqueda de ejemplos y el diseño de algoritmos. De igual manera, se incluyen demostraciones puramente matemáticas de resultados en dichos temas. Sobre el primer problema, en este trabajo se presenta un enfoque para estudiar cuándo podemos teselar un polígono con piezas congruentes. En el mismo capítulo se incluye una demostración asistida por computadora del hecho de que no podemos teselar cuadrados ni rectángulos con una cantidad impar n ≤ 9 y n ≤ 7 de piezas congruentes no rectangulares, respectivamente. Además, se listan todas las teselaciones de cuadrados, con piezas equiangulares no rectangulares, para n ≤ 5. En el siguiente capítulo se incluyen algunos avances en el problema de determinar la mínima dimensión en la que un conjunto de puntos puede realizarse, respetando un orden predefinido sobre sus distancias. El primero es la observación de que un tipo de orden, que había sido expuesto en otro trabajo como no realizable en cierta dimensión, de hecho, puede realizarse en la misma. Para esto se muestra una construcción que funciona en general. El segundo avance es la demostración del hecho que, para órdenes bipartitos con n < m, la mínima dimensión en la que éstos pueden realizarse es n. Además, se incluyen algunos resultados computacionales. El ´ultimo capítulo trata problemas sobre particiones de medidas y conjuntos de puntos en Rd.