El problema de sin tres en línea en geometría discreta plantea la cuestión de cuántos puntos se pueden colocar en una cuadrícula de para que no haya tres puntos en la misma línea recta. Este número está limitado a porque puntos situados sobre los elementos de una cuadrícula incluirían necesariamente una fila con tres o más puntos, debido al conocido principio del palomar. El problema fue introducido por Henry Dudeney en 1900. Brass, Moser y Pach lo denominaron "una de las cuestiones geométricas más antiguas y más estudiadas de puntos colocados sobre una red".
Aunque el problema se ha podido resolver con puntos por cada hasta , se conjetura que se pueden colocar menos de puntos en cuadrículas 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,
Aunque su origen procede de la matemática recreativa, el problema tiene aplicaciones en dibujo de grafos y en el problema del triángulo de Heilbronn.
Primer planteamiento El problema fue planteado por primera vez por Henry Dudeney en 1900, como un rompecabezas de matemáticas recreativas, expresado en términos de colocar los 16 peones de un juego de ajedrez en el tablero de modo que no haya tres en una misma línea recta.The Weekly Dispatch, 29 de abril y 13 de mayo de 1900, citado por. Este es exactamente el problema de sin tres en línea, para el . En una versión posterior del rompecabezas, Dudeney modificó el problema, haciendo que su solución fuera única, al pedir una solución en la que dos de los peones estuvieran en las casillas d4 y e5, atacándose unos a otros en el centro del tablero.
Muchos autores han publicado soluciones a este problema para valores pequeños y en 1998 se sabía que puntos podían colocarse en una cuadrícula de sin dejar tres en línea recta para todo de hasta y para algunos valores mayores. El número de soluciones (sin contar reflexiones y rotaciones como distintas) para valores pequeños de , comenzando con sonOEIS A000769
1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ...
Límites superior e inferior No se conoce el número exacto de puntos que se pueden colocar, como función . Sin embargo, tanto los límites probados como los conjeturados acotan este número dentro de un rango proporcional
Métodos generales de colocación
Una solución ideada por Paul Erdős, publicada por , se basa en la observación de que cuando es un número primo, el conjunto de puntos de la cuadrícula de lado para 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 está contenido Debido a que la diferencia entre dos números primos consecutivos es mucho más pequeña que los propios primos, siempre estará cerca por lo que este método se puede utilizar para colocar puntos en la cuadrícula sin tres puntos colineales.Erdős no publicó esta observación; que apareció mencionada en .
El límite de Erdős se ha mejorado posteriormente: demostró que, cuando es primo, se puede obtener una solución con puntos, colocando puntos en copias múltiples de la hipérbola donde puede elegirse arbitrariamente siempre que sea distinto de cero De nuevo, para arbitrario se puede realizar esta construcción para un número primo próximo a para obtener una solución con
Límite superior Como máximo, los puntos pueden colocarse en una cuadrícula de Si se colocan más puntos, entonces, según el principio del palomar, al menos tres de ellos estarían en la misma línea horizontal de la cuadrícula. Para , se sabe que este límite trivial es correcto.
Límites conjeturados Aunque se pueden colocar exactamente puntos en cuadrículas pequeñas, conjeturó que para cuadrículas grandes, existe un límite superior significativamente menor en la cantidad de puntos que se pueden colocar. Más precisamente, conjeturaron que el número de puntos que se pueden colocar es como máximo una cantidad sublineal mayor siendo
Después de que se descubrió un error en el razonamiento heurístico que condujo 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.Según lo informado por . El descubrimiento de este error fue acreditado por Pegg a Gabor Ellmann.
Aplicaciones Las soluciones al problema de sin tres en línea se pueden usar para evitar ciertos tipos de degeneraciones en dibujo de grafos. El problema al que se aplican implica colocar los vértices de un grafo dado en coordenadas enteras en el plano y dibujar los vínculos del grafo como segmentos rectos. Para ciertos grafos planos, como el problema de los tres servicios, los cruces entre pares de vínculos son inevitables, pero aún se deben evitar las ubicaciones que hacen que un vértice se encuentre situado en un vínculo 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 toda las rectas pasan únicamente a través de dos vértices, y no solamente los segmentos que representan los vínculos quedan libres de otros vértices. El hecho de que el problema de sin tres en línea tenga una solución lineal con muchos puntos se puede traducir en términos de dibujo de grafos en el sentido de que cada grafo, incluso un grafo completo, se puede dibujar sin incidencias de vértices no deseadas usando una cuadrícula cuya el área es cuadrática en el número de vértices, y que para grafos completos no es posible tal dibujo con un área menor que la cuadrática. Los grafos completos también requieren un número lineal de colores en cualquier coloración de grafos, pero otros grafos que pueden ser coloreados con menos colores también se puede dibujar en cuadrículas más pequeñas: si un grafo tiene vértices y una coloración con colores, se puede dibujar en una cuadrícula con área proporcional El dibujo sin tres en línea de un grafo completo es un caso especial de este resultado
El problema de los tres en línea también tiene aplicaciones para otro problema de geometría discreta, el problema del triángulo de Heilbronn. En este problema, se deben 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 de lado dentro del cuadrado unitario, sin tres en una línea recta, entonces por el teorema de Pick cada triángulo tendría un área de la mitad de un cuadrado de cuadrícula. Por lo tanto, resolver una instancia del problema sin tres en línea y luego reducir la cuadrícula de 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 de Paul Erdős para encontrar su solución para el problema de sin 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 los tres puntos en línea.
Generalizaciones y variaciones Subconjuntos de posiciones generales 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 de no 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 un problema de complejidad NP encontrar este subconjunto, para ciertos conjuntos de entrada, y aproximadamente NP su tamaño dentro de un factor constante. Este resultado de dificultad de aproximación se resume diciendo que el problema es de complejidad APX. Si el subconjunto más grande tiene se puede obtener una solución con un algoritmo de aproximación no constante mediante un algoritmo voraz que simplemente elige puntos uno cada vez hasta que todos los puntos restantes se encuentran en líneas a través de pares de puntos elegidos.
Se puede obtener una comprensión más detallada del tiempo de ejecución de los algoritmos para encontrar la solución óptima exacta utilizando complejidad parametrizada, un procedimiento en el que los algoritmos se analizan no solo en términos del tamaño de entrada, sino también en términos de otros parámetros. En este caso, para entradas cuyo subconjunto de posición general más grande tiene se puede encontrar en una cantidad de tiempo que es una función exponencial de multiplicada por un polinomio en la entrada de con el exponente del polinomio que no depende de Problemas con este tipo de tiempo limitado se denominan de complejidad parametrizada.;
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 existencia de estos grandes subconjuntos de posición general se puede convertir en un algoritmo de tiempo lineal para encontrar un subconjunto de posición general cuyo tamaño coincida con el límite de existencia, utilizando una técnica algorítmica conocida como compresión de entropía.
Colocación ávida Repitiendo una sugerencia de , Martin Gardner planteó el problema de obtener el subconjunto más pequeño de una cuadrícula que no se puede extender: no tiene tres puntos en una línea, pero cada sobreconjunto propio forzosamente contiene tres en una línea. De manera equivalente, este es el conjunto más pequeño que podría producir un algoritmo voraz que intentara resolver el problema de sin tres en línea colocando puntos uno cada vez hasta que se atascase. Si solo se consideran líneas paralelas al eje y diagonales, entonces cada uno de estos conjuntos tiene al menos puntos. Sin embargo, se sabe menos sobre la versión del problema donde se consideran todas las líneas: cada ubicación ávida incluye al menos puntos antes de atascarse, pero no se conoce nada mejor que el límite superior trivial .
Dimensiones superiores consideró conjuntos de puntos no colineales en la cuadrícula tridimensional. Demostró que el número máximo de puntos en la cuadrícula sin tres puntos colineales De manera similar a la construcción 2D de Erdős, esto se puede lograr usando los puntos donde es un primo congruente con .
Así como el problema original de sin tres en línea se puede usar para dibujar grafos bidimensionales, esta solución tridimensional se puede usar para dibujar grafos en la cuadrícula tridimensional. Aquí, la condición de no colinealidad significa que un vértice no debe estar en un vínculo no adyacente, pero es normal trabajar con el requisito más estricto de que no se crucen dos vínculos.;;