Problema de sin tres en línea
para que no haya tres puntos en la misma línea recta.
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.
[4] Muchos autores han publicado soluciones a este problema para valores pequeños de
de hasta al menos 46, y para algunos valores mayores.
Sin embargo, tanto los límites probados como los conjeturados acotan este número dentro de un rango proporcional a
no es primo, se puede realizar esta construcción para una cuadrícula
, por lo que este método se puede utilizar para colocar
[8] El límite de Erdős se ha mejorado posteriormente:Hall et al.
puede elegirse arbitrariamente siempre que sea distinto de cero mod
arbitrario se puede realizar esta construcción para un número primo próximo a
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.
puntos en cuadrículas pequeñas,Guy y Kelly (1968) conjeturó que para cuadrículas grandes, existe un límite superior significativamente menor en la cantidad de puntos que se pueden colocar.
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.
puntos en cualquier lugar de un cuadrado unitario, no restringido a una cuadrícula.
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 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
[14] 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.
[15] En geometría computacional, se dice que los conjuntos finitos de puntos sin tres en línea están en posición general.
En este caso, para entradas cuyo subconjunto de posición general más grande tiene tamaño
El ejemplo de la cuadrícula muestra que este límite no se puede mejorar significativamente.
puntos antes de atascarse, pero no se conoce nada mejor que el límite superior trivial
[20] Pór y Wood (2007) consideró conjuntos de puntos no colineales en la cuadrícula tridimensional.
[21] 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.
[23] Sin embargo, no funciona bien usar esta misma idea de elegir puntos cerca de una circunferencia en dos dimensiones: este método encuentra puntos que forman polígonos convexos, que cumplen el requisito de no tener tres en línea, pero son demasiado pequeños.
[24] El problema del conjunto tapa 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 en un espacio vectorial sobre un cuerpo finito en lugar de sobre los números enteros.
Estas líneas extendidas también pueden interpretarse como líneas normales a través de una cuadrícula infinita en el plano euclidiano, tomada según un módulo coincidente con las dimensiones del toro.
Cuando ambas dimensiones son iguales y son primas entre sí, no es posible colocar exactamente un punto en cada fila y columna sin formar un número lineal de tripletas de puntos colineales.
[27] También se han estudiado versiones toroidales de mayor dimensión del problema.
