Un Algoritmo para Recorrer las Celdas de un Arreglo de Rectas

El documento comienza explorando el concepto fundamental de la clasificación de conjuntos de puntos por tipo de orden. Se establece que esta clasificación es computacionalmente ventajosa, ya que la verificación de la orientación de tres puntos se puede realizar de manera rápida. La clave radica en que un conjunto de puntos puede tener solo dos posibles orientaciones, lo que implica una cantidad finita de conjuntos de n puntos con tipos de orden distintos. Esta finitud abre la puerta a la posibilidad de realizar búsquedas de conjuntos con diferentes tipos de orden que cumplan determinadas propiedades usando una computadora. Sin embargo, se destaca que, a pesar de su finitud, la cantidad de conjuntos con tipos de orden distintos es considerablemente grande.

El objetivo principal del documento es presentar un algoritmo que permite recorrer las regiones del plano definidas por tipos de orden invariantes. Este algoritmo facilita la exploración de conjuntos de puntos con propiedades que se mantienen sin importar el tipo de orden. Se estructura en cuatro capítulos, cada uno aportando un elemento crucial para la construcción del algoritmo. El Capítulo 1 sienta las bases de la clasificación por tipo de orden y introduce el concepto de dualidad geométrica, una herramienta esencial en Geometría Combinatoria. El Capítulo 2 describe una estructura de datos que permite mantener la cerradura convexa de un conjunto de puntos mientras se añaden o eliminan puntos. El Capítulo 3 utiliza las herramientas de los capítulos previos para desarrollar el algoritmo de exploración. Finalmente, el Capítulo 4 se centra en la implementación del algoritmo y la presentación de los resultados obtenidos.

El documento explora las aplicaciones prácticas del algoritmo, centrándose en la resolución de problemas que se basan en la invariabilidad bajo tipo de orden. Se mencionan dos heurísticas sencillas para encontrar conjuntos de puntos con un número reducido de hexágonos vacíos o un bajo número de cruces. Estas heurísticas consisten en mover un punto aleatoriamente hasta encontrar una nueva posición que optimice el parámetro estudiado. Se reconoce que el tipo de orden permanece constante dentro de regiones específicas del plano, lo que facilita la búsqueda de soluciones.

El documento destaca la utilidad del algoritmo en diversos problemas de Geometría Combinatoria, incluyendo la conjetura de Erdős-Szekeres (que afirma la existencia de un n-gono en todo conjunto de 2n-2 + 1 puntos en posición general), el problema de determinar la cantidad mínima de puntos necesarios para la aparición de un hexágono vacío o un cuadrilátero monocromático vacío, y la búsqueda de cotas inferiores para el número de cruces en un conjunto de puntos. La capacidad del algoritmo para analizar conjuntos con tipos de orden invariantes lo convierte en una herramienta valiosa para la investigación en este campo. Además, su implementación con Python lo dota de flexibilidad y eficiencia en el procesamiento de datos.