El problema de la regla de carpintero es un problema de geometría discreta , que se puede plantear de la siguiente manera: ¿Se puede mover un polígono plano simple continuamente a una posición donde todos sus vértices estén en posición convexa , de modo que las longitudes de los bordes y la simplicidad se conserven a lo largo del ¿camino? Un problema estrechamente relacionado es mostrar que cualquier cadena poligonal que no se autocruce puede enderezarse, nuevamente mediante una transformación continua que preserva las distancias de los bordes y evita los cruces.
Ambos problemas fueron resueltos con éxito por Connelly, Demaine & Rote (2003) .
Prueba combinatoria
Posteriormente a su trabajo, Ileana Streinu proporcionó una prueba combinatoria simplificada formulada en la terminología de la planificación del movimiento del brazo robótico . Tanto la prueba original como la prueba de Streinu funcionan al encontrar movimientos no expansivos de la entrada, transformaciones continuas de modo que nunca dos puntos se muevan uno hacia el otro. La versión de Streinu de la prueba agrega bordes a la entrada para formar una pseudotriangulación puntiaguda , elimina un borde de casco convexo agregado de este gráfico y muestra que el gráfico restante tiene una familia de movimientos de un parámetro en el que todas las distancias no disminuyen. Al aplicar repetidamente tales movimientos, finalmente se alcanza un estado en el que no son posibles más movimientos expansivos, lo que solo puede suceder cuando la entrada se ha enderezado o convexificado.
Streinu y Whiteley (2005) proporcionan una aplicación de este resultado a las matemáticas del plegado de papel : describen cómo doblar cualquier forma de origami de un solo vértice utilizando solo movimientos simples del papel que no se cruzan por sí mismos. Esencialmente, este proceso de plegado es una versión inversa del problema de convexificar un polígono de longitud menor que π, pero en la superficie de una esfera en lugar de en el plano euclidiano. Este resultado fue ampliado por Panina y Streinu (2010) para polígonos esféricos con una longitud de borde inferior a 2π.
Generalización
John Pardon ( 2009 ) generalizó el problema de la regla de Carpenter a curvas rectificables . Mostró que toda curva de Jordan rectificable se puede hacer convexa, sin aumentar su longitud y sin disminuir la distancia entre ningún par de puntos. Esta investigación, realizada cuando aún era un estudiante de secundaria, ganó el segundo premio de Perdón en Intel Science Talent Search de 2007 ( Cunningham 2007 ).
Ver también
- Flujo de acortamiento de curvas , una transformación continua de una curva cerrada en el plano que finalmente la convexifica
Referencias
- Connelly, Robert ; Demaine, Erik D .; Rote, Günter (2003), "Enderezar arcos poligonales y convexificar ciclos poligonales" (PDF) , Geometría discreta y computacional , 30 (2): 205-239, doi : 10.1007 / s00454-003-0006-7 , MR 1931840. La versión preliminar apareció en el 41o Simposio Anual sobre Fundamentos de la Ciencia de la Computación , 2000.
- Cunningham, Aimee (17 de marzo de 2007), "The Next Generation", Science News : 166.
- Streinu, Ileana (2000), "Un enfoque combinatorio para la planificación del movimiento del brazo robótico plano sin colisión" , Actas del 41º Simposio anual sobre fundamentos de la informática , IEEE Computer Society, págs. 443–453, doi : 10.1109 / SFCS. 2000.892132 , MR 1931841[ enlace muerto permanente ]
- Panina, Gaiane; Streinu, Ileana (2010), "Aplanamiento del origami de vértice único: el caso no expansivo", Geometría computacional: teoría y aplicaciones , 43 (8): 678–687, arXiv : 1003.3490 , doi : 10.1016 / j.comgeo.2010.04 0.002 , MR 1931841
- Perdón, John (2009), "Sobre el despliegue de curvas cerradas simples", Transactions of the American Mathematical Society , 361 (4): 1749-1764, arXiv : 0809.1404 , doi : 10.1090 / S0002-9947-08-04781-8 , MR 2465815.
- Streinu, Ileana ; Whiteley, Walter (2005), "Origami de vértice único y movimientos expansivos esféricos", Geometría discreta y computacional: Conferencia japonesa, JCDCG 2004, Tokio, Japón, 8-11 de octubre de 2004, Artículos seleccionados revisados , Notas de conferencias en Ciencias de la Computación, 3742 , Springer-Verlag, págs. 161-173, MR 2212105
enlaces externos
- Página de Erik Demaine con animaciones del movimiento de enderezamiento aplicado a algunos enlaces