Problema de sin tres en línea

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 $n\times n$ para que no haya tres puntos en la misma línea recta. Este número está limitado a $2n$ como máximo, porque $2n+1$ 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".​

Un conjunto de 20 puntos en una cuadrícula de 10 × 10, dispuestos de forma que no haya tres puntos sobre la misma línea recta de la cuadrícula

Aunque el problema se ha podido resolver con $2n$ puntos por cada $n$ hasta al menos $46$, se conjetura que se pueden colocar menos de $2n$ 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 $3n/2$ puntos, pero no $2n$.

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.​ Este es exactamente el problema de sin tres en línea, para el caso de $n=8$.​. 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 de $n$,​ y en 1998 se sabía que $2n$ puntos podían colocarse en una cuadrícula de $n\times n$ sin dejar tres en línea recta para todo $n$ de hasta al menos 46, y para algunos valores mayores.​ El número de soluciones (sin contar reflexiones y rotaciones como distintas) para valores pequeños de $n$, comenzando con desde $n=2$, son​​

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (sucesión A000769 en OEIS)

Límites superior e inferior

No se conoce el número exacto de puntos que se pueden colocar, como función de $n$,. Sin embargo, tanto los límites probados como los conjeturados acotan este número dentro de un rango proporcional a $n$.

Métodos generales de colocación

Colocación subóptima de $11$ puntos en una cuadrícula de $12\times 12$, utilizando el método de Erdős. El primo más grande $p$ menor que el tamaño de la cuadrícula es $p=11$; la solución coloca los puntos en las coordenadas $(i,i^{2}$ mod $p)$ para $i=0,1,\dots p-1$. Por ejemplo, se incluye $(4,5)$ porque $4^{2}=16\cong 5$ (${\displaystyle }$mod $11$)

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

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

Límite superior

Como máximo, los $2n$ puntos pueden colocarse en una cuadrícula de tamaño $n$. 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 $n\leq 46$, se sabe que este límite trivial es correcto.​

Límites conjeturados

Aunque se pueden colocar exactamente $2n$ 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. Más precisamente, conjeturaron que el número de puntos que se pueden colocar es como máximo una cantidad sublineal mayor de $cn$, siendo​

$$c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.$$

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 $cn$ con​.

$$c={\frac {\pi }{\sqrt {3}}}\approx 1.814.$$

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 $n$ vértices y una coloración con $k$ colores, se puede dibujar en una cuadrícula con área proporcional a $nk$. El dibujo sin tres en línea de un grafo completo es un caso especial de este resultado con $k=n$.​

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 $n$ 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 $\varepsilon$ 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 al menos $\varepsilon ^{2}/2$, 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 $\Omega (1/n^{2})$. 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 tamaño $k$, se puede obtener una solución con un algoritmo de aproximación $O({\sqrt {k}})$ 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 tamaño $k$, se puede encontrar en una cantidad de tiempo que es una función exponencial de $k$ multiplicada por un polinomio en la entrada de tamaño $n$, con el exponente del polinomio que no depende de $k$. Problemas con este tipo de tiempo limitado se denominan de complejidad parametrizada.​

Para conjuntos de $S$ puntos que tienen como máximo ${\textstyle \ell }$ puntos por línea, con ${\textstyle \ell =O({\sqrt {|S|}})}$, existen subconjuntos de posición general de tamaño casi proporcional a ${\textstyle \ell =O({\sqrt {|S|}})}$. 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 de $S$, 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 Adena, Holton y Kelly (1974), Martin Gardner planteó el problema de obtener el subconjunto más pequeño de una cuadrícula $n\times n$ 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 $n-1$ 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 $\Omega (n^{2/3})$ puntos antes de atascarse, pero no se conoce nada mejor que el límite superior trivial $2n$.​

Dimensiones superiores

Pór y Wood (2007) consideró conjuntos de puntos no colineales en la cuadrícula tridimensional. Demostró que el número máximo de puntos en la cuadrícula $n\times n\times n$ sin tres puntos colineales es $\Theta (n^{2})$. De manera similar a la construcción 2D de Erdős, esto se puede lograr usando los puntos $(x,y,x^{2}+y^{2}$ mod $p)$, donde $p$ es un primo congruente con 3 mod 4.​

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.​

En dimensiones mucho más altas, se han utilizado conjuntos de puntos de cuadrícula sin tres en línea, obtenidos eligiendo puntos cerca de una n-esfera, para encontrar conjuntos de Salem-Spencer grandes, conjuntos de números enteros sin tres en línea que formen una progresión aritmética.​ 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. Los polígonos convexos más grandes con vértices en una cuadrícula de $n\times n$ tienen solo $O(n^{2/3})$ vértices.​ 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.​

Superficie toroidal

Otra variación del problema consiste en convertir la cuadrícula en un toroide discreto mediante el uso de condiciones de frontera periódicas, en el que el lado izquierdo del toroide 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 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. Para un toro basado en una cuadrícula $m\times n$, el número máximo de puntos que se pueden elegir sin tres en línea es como máximo de $2\gcd(m,n)$.​. 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.​ También se han estudiado versiones toroidales de mayor dimensión del problema.​

Bibliografía

• Adena, Michael A.; Holton, Derek A.; Kelly, Patrick A. (1974). «Some thoughts on the no-three-in-line problem». En Holton, Derek A., ed. Combinatorial Mathematics: Proceedings of the Second Australian Conference (University of Melbourne, 1973). Lecture Notes in Mathematics 403. pp. 6-17. MR 0349396. doi:10.1007/BFb0057371. 
• Aichholzer, Oswin; Eppstein, David; Hainzl, Eva-Maria (January 2023). «Geometric dominating sets – a minimum version of the No-Three-In-Line Problem». Computational Geometry (Elsevier) 108. doi:10.1016/j.comgeo.2022.101913. 
• Anderson, David Brent (1979). «Update on the no-three-in-line problem». Journal of Combinatorial Theory. Series A 27 (3): 365-366. MR 555806. doi:10.1016/0097-3165(79)90025-6. 
• Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna et al. (2007). «On simultaneous planar graph embeddings». Computational Geometry 36 (2): 117-130. MR 2278011. doi:10.1016/j.comgeo.2006.05.006. 
• Brass, Peter; Moser, William; Pach, János (2005). «Section 10.1: Packing lattice points in subspaces». Research Problems in Discrete Geometry. Springer, New York. pp. 417-421. ISBN 978-0-387-29929-7. MR 2163782. 
• Cooper, Alec S.; Pikhurko, Oleg; Schmitt, John R.; Warrington, Gregory S. (2014). «Martin Gardner's minimum no-3-in-a-line problem». American Mathematical Monthly 121 (3): 213-221. JSTOR 10.4169/amer.math.monthly.121.03.213. S2CID 887220. arXiv:1206.5350. doi:10.4169/amer.math.monthly.121.03.213. 
• Cooper, Joshua N.; Solymosi, József (2005). «Collinear points in permutations». Annals of Combinatorics 9 (2): 169-175. MR 2153735. S2CID 11035679. arXiv:math/0408396. doi:10.1007/s00026-005-0248-4. 
• Craggs, D.; Hughes-Jones, R. (1976). «On the no-three-in-line problem». Journal of Combinatorial Theory. Series A 20 (3): 363-364. MR 406804. doi:10.1016/0097-3165(76)90030-3. 
• Solución Dudeney, Henry (1917). «317. A puzzle with pawns». Amusements in Mathematics. Edinburgh: Nelson. p. 94. , p. 222. Publicado originalmente en el Tribune de Londres, el 7 de noviembre de 1906.
• Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). «Computing straight-line 3d grid drawings of graphs in linear volume». Computational Geometry: Theory and Applications 32 (1): 26-58. doi:10.1016/j.comgeo.2004.11.003. 
• Dujmović, Vida; Morin, Pat; Wood, David R. (2005). «Layout of graphs with bounded tree-width». SIAM Journal on Computing 34 (3): 553-579. S2CID 3264071. arXiv:cs/0406024. doi:10.1137/S0097539702416141. 
• Elkin, Michael (2011). «An improved construction of progression-free sets». Israel Journal of Mathematics 184: 93-128. MR 2823971. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. 
• Eppstein, David (2018). «Chapter 9: General position». Forbidden Configurations in Discrete Geometry. Cambridge University Press. pp. 72-86. 
• Flammenkamp, Achim (1992). «Progress in the no-three-in-line problem». Journal of Combinatorial Theory. Series A 60 (2): 305-311. doi:10.1016/0097-3165(92)90012-J. 
• Flammenkamp, Achim (1998). «Progress in the no-three-in-line problem, II». Journal of Combinatorial Theory. Series A 81 (1): 108-113. doi:10.1006/jcta.1997.2829. 
• Froese, Vincent; Kanj, Iyad; Nichterlein, André; Niedermeier, Rolf (2017). «Finding points in general position». International Journal of Computational Geometry & Applications 27 (4): 277-296. MR 3766097. S2CID 47260245. arXiv:1508.01097. doi:10.1142/S021819591750008X. 
• Gardner, Martin (October 1976). «Combinatorial problems, some old, some new and all newly attacked by computer». Mathematical Games. Scientific American 235 (4): 131-137. JSTOR 24950467. 
• Guy, R. K.; Kelly, P. A. (1968). «The no-three-in-line problem». Canadian Mathematical Bulletin 11 (4): 527-531. MR 0238765. doi:10.4153/CMB-1968-062-3. 
• Hall, R. R.; Jackson, T. H.; Sudbery, A.; Wild, K. (1975). «Some advances in the no-three-in-line problem». Journal of Combinatorial Theory. Series A 18 (3): 336-341. doi:10.1016/0097-3165(75)90043-6. 
• Harborth, Heiko; Oertel, Philipp; Prellberg, Thomas (1989). «No-three-in-line for seventeen and nineteen». Proceedings of the Oberwolfach Meeting “Kombinatorik” (1986). Discrete Mathematics 73 (1–2): 89-90. MR 974815. doi:10.1016/0012-365X(88)90135-5. 
• Jarník, Vojtěch (1926). «Über die Gitterpunkte auf konvexen Kurven» [On the grid points on convex curves]. Mathematische Zeitschrift (en alemán) 24 (1): 500-518. MR 1544776. S2CID 117747514. doi:10.1007/BF01216795. 
• Klarreich, Erica (31 de mayo de 2016). «Simple Set Game Proof Stuns Mathematicians». Quanta. 
• Kløve, Torleiv (1978). «On the no-three-in-line problem. II». Journal of Combinatorial Theory. Series A 24 (1): 126-127. MR 462998. doi:10.1016/0097-3165(78)90053-5. 
• Kløve, Torleiv (1979). «On the no-three-in-line problem. III». Journal of Combinatorial Theory. Series A 26 (1): 82-83. MR 525088. doi:10.1016/0097-3165(79)90055-4. 
• Komlós, J.; Pintz, J.; Szemerédi, E. (1982). «A lower bound for Heilbronn's problem». London Mathematical Society 25 (1): 13-24. MR 0645860. doi:10.1112/jlms/s2-25.1.13. 
• Knuth, Donald E. (2008). «Answer to exercise 242». The Art of Computer Programming, Fascicle 1b: A Draft of Section 7.1.4: Binary Decision Diagrams. p. 130. 
• Ku, Cheng Yeaw; Wong, Kok Bin (2018). «On no-three-in-line problem on m-dimensional torus». Graphs and Combinatorics 34 (2): 355-364. MR 3774457. S2CID 3935268. doi:10.1007/s00373-018-1878-8. 
• Misiak, Aleksander; Stępień, Zofia; Szymaszkiewicz, Alicja; Szymaszkiewicz, Lucjan; Zwierzchowski, Maciej (2016). «A note on the no-three-in-line problem on a torus». Discrete Mathematics 339 (1): 217-221. MR 3404483. S2CID 40210322. arXiv:1406.6713. doi:10.1016/j.disc.2015.08.006. 
• Pach, János; Thiele, Torsten; Tóth, Géza (1998). «Three-dimensional grid drawings of graphs». Graph Drawing, 5th Int. Symp., GD '97. Lecture Notes in Computer Science 1353. Springer-Verlag. pp. 47-51. doi:10.1007/3-540-63938-1_49. 
• Payne, Michael S.; Wood, David R. (2013). «On the general position subset selection problem». SIAM Journal on Discrete Mathematics 27 (4): 1727-1733. MR 3111653. S2CID 7164626. arXiv:1208.5289. doi:10.1137/120897493. 
• Pegg, Ed Jr. (11 de abril de 2005). «Chessboard Tasks». Math Games. Mathematical Association of America. Consultado el 25 de junio de 2012. 
• Pór, Attila; Wood, David R. (2007). «No-three-in-line-in-3D». Algorithmica 47 (4): 481. S2CID 209841346. doi:10.1007/s00453-006-0158-9. 
• Roth, K. F. (1951). «On a problem of Heilbronn». London Mathematical Society 26 (3): 198-204. doi:10.1112/jlms/s1-26.3.198. 
• Wood, David R. (2005). «Grid drawings of k-colourable graphs». Computational Geometry: Theory and Applications 30 (1): 25-28. doi:10.1016/j.comgeo.2004.06.001. 

Enlaces externos

• Flammenkamp, Achim. «The No-Three-in-Line Problem». 
• Weisstein, Eric W. «No-Three-in-a-Line-Problem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q6580594