No hay problema de tres en línea - No-three-in-line problem

El problema de no tres en línea en geometría discreta pregunta cuántos puntos se pueden colocar en la cuadrícula para que no haya tres puntos en la misma línea. Este número es como máximo , porque los puntos en una cuadrícula incluirían una fila de tres o más puntos, según el principio de casillero . El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo llaman "una de las cuestiones geométricas más antiguas y estudiadas sobre los puntos de celosía". ${\ Displaystyle n \ times n}$${\ Displaystyle 2n}$${\ Displaystyle 2n + 1}$

Aunque el problema se puede resolver con puntos por cada hasta que , se conjetura que menos puntos se pueden colocar en las redes de gran tamaño. Los métodos conocidos pueden colocar linealmente muchos puntos en cuadrículas de tamaño arbitrario, pero el mejor de estos métodos coloca un poco menos de puntos, no . También se han estudiado varios problemas relacionados con la búsqueda de puntos sin tres en línea, entre otros conjuntos de puntos distintos de las cuadrículas. ${\ Displaystyle 2n}$${\ Displaystyle n}$${\ displaystyle 46}$${\ Displaystyle 2n}$${\ Displaystyle 3n / 2}$${\ Displaystyle 2n}$

Aunque tiene su origen en las matemáticas recreativas , el problema tiene aplicaciones en el dibujo de gráficos y en el problema del triángulo de Heilbronn .

Pequeñas instancias

El problema fue planteado por primera vez por Henry Dudeney en 1900, como un rompecabezas en matemáticas recreativas, expresado en términos de colocar los 16 peones de un tablero de ajedrez en el tablero de modo que no haya tres en una línea. Este es exactamente el problema de no tres en línea, para el caso . ${\ Displaystyle n = 8}$En una versión posterior del rompecabezas, Dudeney modificó el problema, haciendo que su solución fuera única, pidiendo una solución en la que dos de los peones estén en las casillas d4 y e5 , atacándose entre sí en el centro del tablero.

Muchos autores han publicado soluciones a este problema para valores pequeños de ,${\ Displaystyle n}$ y en 1998 se sabía que los puntos podían colocarse en una cuadrícula sin tres en una línea para todos hasta 46, y algunos valores más grandes. El número de soluciones (sin contar las reflexiones y rotaciones como distintas) para valores pequeños de , a partir de , son ${\ Displaystyle 2n}$${\ Displaystyle n \ times n}$${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle n = 2}$

Límites superior e inferior

El número exacto de puntos que se puede colocar, como una función de ,${\ Displaystyle n}$ no se conoce. Sin embargo, tanto los límites probados como los conjeturados limitan este número dentro de un rango proporcional a .${\ Displaystyle n}$

Métodos generales de colocación

Una solución de Paul Erdős , publicada por Roth (1951) , se basa en la observación de que cuando es un número primo , el conjunto de puntos de la cuadrícula mod , por , no contiene tres puntos colineales. Cuando no es primo, se puede realizar esta construcción para una cuadrícula contenida en la cuadrícula, donde es el primo más grande que es como máximo . Debido a que el espacio entre primos consecutivos es mucho más pequeño que los primos mismos, siempre estará cerca de , por lo que este método se puede usar para colocar puntos en la cuadrícula sin tres puntos colineales. ${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle (yo, yo ^ {2}}$${\ Displaystyle n)}$${\ Displaystyle 0 \ leq i <n}$${\ Displaystyle n}$${\ Displaystyle p \ times p}$${\ Displaystyle n \ times n}$${\ Displaystyle p}$${\ Displaystyle n}$${\ Displaystyle p}$${\ Displaystyle n}$${\ Displaystyle no (n)}$${\ Displaystyle n \ times n}$

El límite de Erdős se ha mejorado posteriormente: Hall et al. (1975) muestran que, cuando es primo, se puede obtener una solución con puntos, colocando puntos en múltiples copias de la hipérbola (mod ), donde se puede elegir arbitrariamente siempre que sea un mod distinto de cero . Nuevamente, por arbitrario se puede realizar esta construcción para un primo cercano para obtener una solución con puntos.${\ Displaystyle n / 2}$${\ Displaystyle 3 (n-2) / 2}$ ${\ Displaystyle xy = k}$ ${\ Displaystyle n / 2}$${\ Displaystyle k}$${\ Displaystyle n / 2}$${\ Displaystyle n}$${\ Displaystyle n / 2}$${\ Displaystyle {\ tfrac {3} {2}} no (n)}$

Límite superior

En la mayoría de los puntos se pueden colocar en una cuadrícula de cualquier tamaño . Porque, si se colocan más puntos, entonces, según el principio del casillero, unos tres de ellos estarían todos en la misma línea horizontal de la cuadrícula. Para valores suficientemente pequeños de , este límite trivial es estrecho. ${\ Displaystyle 2n}$${\ Displaystyle n}$${\ Displaystyle n}$

Límites conjeturados

Aunque se pueden colocar exactamente puntos en cuadrículas pequeñas, Guy y Kelly (1968) conjeturaron que para cuadrículas grandes, existe un límite superior significativamente más pequeño en el número de puntos que se pueden ubicar. Más precisamente, conjeturaron que el número de puntos que se pueden colocar es como máximo una cantidad sublineal mayor que , con ${\ Displaystyle 2n}$${\ displaystyle cn}$

Después de que se descubrió un error en el razonamiento heurístico que llevó a esta conjetura, Guy corrigió el error e hizo la conjetura más fuerte de que no se puede hacer más que sublinealmente mejor que con ${\ displaystyle cn}$

Aplicaciones

Se pueden usar soluciones al problema de no tres en línea para evitar ciertos tipos de degeneraciones en el dibujo de gráficos . El problema al que se aplican implica colocar los vértices de un gráfico dado en coordenadas enteras en el plano y dibujar los bordes del gráfico como segmentos de línea recta . Para ciertos gráficos, como el gráfico de utilidad , los cruces entre pares de aristas son inevitables, pero aún así se deben evitar las ubicaciones que hacen que un vértice se encuentre en una arista a través de otros dos vértices. Cuando los vértices se colocan sin tres en línea, este tipo de ubicación problemática no puede ocurrir, porque la línea completa a través de dos vértices cualesquiera, y no solo el segmento de línea, está libre de otros vértices. El hecho de que el problema sin tres en línea tenga una solución con muchos puntos lineales se puede traducir en términos de dibujo de gráficos, lo que significa que cada gráfico, incluso un gráfico completo , se puede dibujar sin incidencias no deseadas en el borde del vértice utilizando una cuadrícula cuyo el área es cuadrática en el número de vértices, y que para gráficos completos no es posible dibujar con un área menor que cuadrática. Los gráficos completos también requieren un número lineal de colores en cualquier color de gráfico , pero otros gráficos que se pueden colorear con menos colores también se pueden dibujar en cuadrículas más pequeñas: si un gráfico tiene vértices y un gráfico para colorear con colores, se puede dibujar en una cuadrícula con área proporcional a . El dibujo sin tres en línea de un gráfico completo es un caso especial de este resultado con .${\ Displaystyle n}$${\ Displaystyle k}$${\ Displaystyle nk}$${\ Displaystyle k = n}$

El problema de no tres en línea también tiene aplicaciones a otro problema en geometría discreta, el problema del triángulo de Heilbronn . En este problema, uno debe colocar puntos, en cualquier lugar de un cuadrado unitario, no restringido a una cuadrícula. El objetivo de la ubicación es evitar triángulos de área pequeña y, más específicamente, maximizar el área del triángulo más pequeño formado por tres de los puntos. Por ejemplo, una ubicación con tres puntos en línea sería muy mala según este criterio, porque estos tres puntos formarían un triángulo degenerado con área cero. Por otro lado, si los puntos se pueden colocar en una cuadrícula de longitud lateral dentro del cuadrado unitario, sin tres en una línea, entonces, según el teorema de Pick, cada triángulo tendría un área al menos , la mitad de un cuadrado de la cuadrícula. Por lo tanto, resolver una instancia del problema sin tres en línea y luego escalar la cuadrícula de números enteros para que quepa dentro de un cuadrado unitario produce soluciones al problema del triángulo de Heilbronn donde el triángulo más pequeño tiene un área . Esta aplicación fue la motivación para que Paul Erdős encontrara su solución para el problema de no tres en línea. Siguió siendo el mejor límite inferior de área conocido para el problema del triángulo de Heilbronn desde 1951 hasta 1982, cuando se mejoró mediante un factor logarítmico utilizando una construcción que no se basaba en el problema de no tres en línea. ${\ Displaystyle n}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon ^ {2} / 2}$${\ Displaystyle \ Omega (1 / n ^ {2})}$

Generalizaciones y variaciones

Subconjuntos de posición general

En geometría computacional , se dice que los conjuntos finitos de puntos sin tres en línea están en posición general . En esta terminología, el problema sin tres en línea busca el subconjunto más grande de una cuadrícula que está en posición general, pero los investigadores también han considerado el problema de encontrar el subconjunto de posición general más grande de otros conjuntos de puntos que no son de cuadrícula. Es NP-difícil encontrar este subconjunto, para ciertos conjuntos de entrada, y difícil aproximar su tamaño dentro de un factor constante; esta dureza del resultado de aproximación se resume diciendo que el problema es APX-hard . Si el subconjunto más grande tiene tamaño , se puede obtener${\ Displaystyle k}$ una solución con la relación de aproximación no constante mediante un algoritmo codicioso que simplemente elige puntos uno a la vez hasta que todos los puntos restantes se encuentran en líneas a través de pares de puntos elegidos. ${\ Displaystyle O ({\ sqrt {k}})}$

Se puede obtener una comprensión más detallada del tiempo de ejecución de los algoritmos para encontrar la solución óptima exacta mediante el uso de la complejidad parametrizada , en la que los algoritmos se analizan no solo en términos del tamaño de entrada, sino en términos de otros parámetros de la entrada. En este caso, para las entradas cuyo subconjunto de posición general más grande tiene tamaño ,${\ Displaystyle k}$ se puede encontrar en una cantidad de tiempo que es una función exponencial de multiplicado por un polinomio en el tamaño de la entrada , sin que el exponente del polinomio dependa de . Los problemas con este tipo de límite de tiempo se denominan manejables con parámetros fijos . ${\ Displaystyle k}$${\ Displaystyle n}$${\ Displaystyle k}$

Para conjuntos de puntos que tienen como máximo puntos por línea, con , existen subconjuntos de posición general de tamaño casi proporcional a . El ejemplo de la cuadrícula muestra que este límite no se puede mejorar significativamente. La prueba de la existencia de estas grandes subconjuntos de posición general se puede convertir en un de tiempo polinómico algoritmo para encontrar un subconjunto-posición general de , de juego del tamaño la existencia atado, utilizando una técnica algorítmica conocida como compresión entropía . ${\ Displaystyle S}$${\ textstyle \ ell}$${\ estilo de texto \ ell = O ({\ sqrt {| S |}})}$${\ estilo de texto \ ell = O ({\ sqrt {| S |}})}$${\ Displaystyle S}$

Colocación codiciosa

Repitiendo una sugerencia de Adena, Holton y Kelly (1974) , Martin Gardner pidió el subconjunto más pequeño de una cuadrícula que no se pueda extender: no tiene tres puntos en una línea, pero cada superconjunto adecuado tiene tres en una línea. De manera equivalente, este es el conjunto más pequeño que podría producir un algoritmo codicioso que intenta resolver el problema de no tres en línea colocando puntos uno a la vez hasta que se atasca. Si solo se consideran las líneas diagonales y paralelas al eje, entonces cada conjunto de este tipo tiene al menos puntos. Sin embargo, se sabe menos sobre la versión del problema en la que se consideran todas las líneas: cada ubicación codiciosa incluye al menos puntos antes de atascarse, pero no se conoce nada mejor que el límite superior trivial . ${\ Displaystyle n \ times n}$${\ Displaystyle n-1}$${\ Displaystyle \ Omega (n ^ {2/3})}$${\ Displaystyle 2n}$

Mayores dimensiones

Pór & Wood (2007) consideraron conjuntos de puntos no colineales en la cuadrícula tridimensional . Demostraron que el número máximo de puntos en la cuadrícula sin tres puntos colineales es . De manera similar a la construcción 2D de Erdős, esto se puede lograr usando mod de puntos , donde es un primo congruente con 3 mod 4 . Así como el problema original sin tres en línea se puede usar para dibujar gráficos bidimensionales, se puede usar esta solución tridimensional para dibujar gráficos en la cuadrícula tridimensional. Aquí, la condición de no colinealidad significa que un vértice no debe estar en un borde no adyacente, pero es normal trabajar con el requisito más estricto de que no se crucen dos bordes. ${\ Displaystyle n \ times n}$${\ Displaystyle \ Theta (n ^ {2})}$${\ Displaystyle (x, y, x ^ {2} + y ^ {2}}$${\ Displaystyle p)}$${\ Displaystyle p}$

En dimensiones mucho más altas, conjuntos de puntos de la cuadrícula sin tres en línea, obtenidos eligiendo puntos cerca de una hiperesfera , se han utilizado para encontrar grandes conjuntos de Salem-Spencer , conjuntos de números enteros sin tres que forman una progresión aritmética. Sin embargo, no funciona bien usar esta misma idea de elegir puntos cerca de un círculo en dos dimensiones: este método encuentra puntos que forman polígonos convexos, que satisfacen el requisito de no tener tres en línea, pero son demasiado pequeños. Los polígonos convexos más grandes con vértices en una cuadrícula solo tienen vértices. El problema del conjunto de límites se refiere a un problema similar al problema de no tres en línea en espacios que son de alta dimensión y se basan como espacios vectoriales sobre campos finitos en lugar de sobre los números enteros. ${\ Displaystyle n \ times n}$${\ Displaystyle O (n ^ {2/3})}$

Toro

Otra variación del problema implica convertir la cuadrícula en un toro discreto mediante el uso de condiciones de contorno periódicas en las que el lado izquierdo del toro está conectado al lado derecho y el lado superior está conectado al lado inferior. Esto tiene el efecto, en las líneas inclinadas a través de la cuadrícula, de conectarlas en líneas más largas a través de más puntos y, por lo tanto, dificulta la selección de puntos con un máximo de dos de cada línea. Estas líneas extendidas también se pueden interpretar como líneas normales a través de una cuadrícula infinita en el plano euclidiano, tomado en módulo las dimensiones del toro. Para un toro basado en una cuadrícula, el número máximo de puntos que se pueden elegir sin tres en línea es como máximo . Cuando ambas dimensiones son iguales y primas, no es posible colocar exactamente un punto en cada fila y columna sin formar un número lineal de triples colineales. También se han estudiado versiones toroidales de dimensiones superiores del problema. ${\ Displaystyle m \ times n}$${\ Displaystyle 2 \ gcd (m, n)}$

Notas

Referencias

enlaces externos

• Flammenkamp, ​​Achim. "El problema de los tres en línea" .
• Weisstein, Eric W. "Ningún problema de tres en una línea" . MathWorld .