Línea de tiempo para Algoritmo que determine la cantidad mínima de lineas que intersecten a todas las lineas de un plano
Licencia actual CC BY-SA 4.0
8 eventos
cuándo alternar formato | qué | por | licencia | comentario | |
---|---|---|---|---|---|
el 6 feb. 2019 a las 18:43 | historial | editado | Patricio Moracho | CC BY-SA 4.0 |
se añadieron 619 caracteres en el cuerpo
|
el 6 feb. 2019 a las 12:33 | comentario | añadido | Patricio Moracho | @abulafia, eso es cierto | |
el 6 feb. 2019 a las 12:32 | comentario | añadido | abulafia | Sí, lo de que dos diagonales seguro cortarán todas lo veía claro. Lo que muestro esta figura es que tu método de usar una o dos diagonales, no da siempre una solución "optima" en el sentido de generar el mínimo de cortes. En el caso de la figura das como solución dos cortes (las dos diagonales), pero podía resolverse con uno solo (por ejemplo una vertical que pase por x=0.5) | |
el 6 feb. 2019 a las 12:10 | comentario | añadido | Patricio Moracho | El otro problema, serían las lineas que pasan justo sobre la diagonal, no podemos decir que la propia diagonal la corta, pero la otra diagonal si. De ahí que afirmo que dos diagonales es el número mínimo seguro para cualquier configuración, eventualmente una sola puede resolverlo | |
el 6 feb. 2019 a las 12:07 | comentario | añadido | Patricio Moracho | @abulafia, lamentablemente no sé, ni pude encontrar un teorema que diga que todas la líneas tal como las define el OP van a ser cortadas por las dos diagonales. Pero si lo piensas gráficamente, una sola diagonal construye dos triángulos, cualquiera de la lineas que nacen de alguno de estos catetos y vayan a cualquiera de los catetos del otro triangulo van a pasar (y cortar) por la hipotenusa (diagonal) .. salvo las que van de un cateto al otro pero del mismo triangulo, en estas es dónde la otra diagonal tiene sentido. | |
el 6 feb. 2019 a las 11:05 | comentario | añadido | abulafia | De hecho, sí hay tal caso: i.sstatic.net/88Uhp.png Pero releyendo la pregunta veo que no pide el número mínimo de cortes, por lo que tu solución con dos diagonales sigue siendo válida. | |
el 6 feb. 2019 a las 10:52 | comentario | añadido | abulafia | Bien visto! +1 Pero me queda la duda ¿habrá algún caso en el que una diagonal no intersecte todas las líneas, (y tu solución producirá dos diagonales), pero había otra recta que sí las intersectaba todas? ¿Será posible demostrar que tal caso no existe? | |
el 6 feb. 2019 a las 3:35 | historial | respuesta | Patricio Moracho | CC BY-SA 4.0 |