Ejemplos en los que la información de la geometría fue útil para resolver algo completamente no geométrico

Una de las cosas buenas de haber evolucionado en un universo con tres dimensiones espaciales es que hemos desarrollado habilidades para resolver problemas relacionados con objetos en el espacio. Así, por ejemplo, podemos pensar en un triplete de números como un punto en 3-d y, por lo tanto, en un cálculo sobre tripletas de números como un cálculo sobre puntos en 3-d, que luego se puede resolver utilizando nuestra intuición sobre el espacio. Esto parece sugerir que a veces debería ser posible resolver un problema completamente no geométrico utilizando técnicas de geometría. ¿Alguien sabe de tales ejemplos?

Por supuesto, los términos "geométrico" y "no geométrico" son ligeramente vagos aquí. Se puede argumentar que cualquier problema geométrico es en realidad no geométrico si reemplaza todos los puntos con sus coordenadas. Pero intuitivamente, la definición es clara. Digamos que llamamos algo geométrico si consideramos enviar un documento al respecto a SoCG.

Algunos ejemplos más:

Sleator, Thurston y Tarjan utilizaron una representación geométrica de árboles como particiones de polígonos y geometría hiperbólica, para probar los límites inferiores para la rotación de árboles binarios . (Además, creo que la historia de un árbol dinámico de búsqueda binaria se puede representar como una tetraédrica).

La reducción del antepasado menos común al rango de consultas mínimas , debido a Berkman y Vishkin, relaciona un problema de estructuras de datos en árboles con un problema posiblemente geométrico. (y gracias por el artículo David)

La reducción de un problema de programación a un conjunto independiente de peso máximo de rectángulos paralelos al eje [1] o la reducción de un problema de programación diferente a una cubierta de conjunto geométrico [2] podría calificar.

La reducción del mayor problema de subsecuencia común a la búsqueda de capas de máximos es bien conocida (es decir, soy demasiado vago para buscar quién realmente lo pensó).

[1] (Liane Lewin-Eytan, Joseph Seffi Naor y Ariel Orda)

[2] Nikhil Bansal, Kirk Pruhs. La geometría de la programación, FOCS 2010.

[editar más tarde] Un par de casos más donde una vista "geométrica" ​​parecía sorprendente (aunque probablemente no se cumplan los estándares de "sumisión a SoCG" o "hace que algo se visualice"):

topología algebraica aplicada a límites inferiores para computación distribuida

Incorporando la computabilidad en la dimensión de Hausdorff

definiendo una noción de distancia para grupos, luego volumen, luego crecimiento de volumen en función de la distancia, luego usando "crecimiento polinómico"

$\ell_1$

También se mencionaron en otro lugar, pero un ejemplo que me gusta es el siguiente: ordenar con información parcial es el problema de encontrar una extensión lineal desconocida fija de un poset, dado el poset y usar el número de consultas de comparación lo más cerca posible de la información teórica. límite inferior (esto es solo ordenar cuando el número de comparaciones es la medida crítica de complejidad y algunas comparaciones se dan de forma gratuita). Saks y Kahn demostraron la existencia de estrategias de comparación óptimas (hasta constantes) utilizando las propiedades del politopo de orden, un politopo especial asociado con un poset (puede encontrar una gran exposición en el libro Lectures on Discrete Geometry de Matousek). El primer algoritmo de tiempo polinómico (por Kahn y Kim) que calcula una estrategia de comparación óptima (hasta una constante) nuevamente utilizó las propiedades del politopo de orden, así como el politopo de conjunto estable del gráfico de incompatibilidad del poset de entrada.

Hay un artículo relativamente reciente de Demaine et al que utiliza una representación geométrica de árboles de búsqueda binarios para avanzar en el estado del arte en la optimización dinámica. Estoy siendo un poco vago aquí porque no resuelven la conjetura de OD: pero sí fortalecen algunos límites y dan algunas nuevas ideas que parecen provenir de la formulación geométrica.

No creo que haya ejemplos de tales cosas. Excepto para la programación lineal, la programación semi-definida, números complejos, grandes fracciones de aprendizaje automático, etc. La verdadera pregunta es http://www.youtube.com/watch?v=ExWfh6sGyso .

Hubo un buen artículo en POPL el año pasado, EigenCFA: acelerar el análisis de flujo con GPU , que representaba términos lambda como matrices y luego usaba GPU para realizar rápidamente análisis de flujo de datos en ellos.

El documento no señaló esto explícitamente, pero lo que básicamente estaban haciendo era explotar la estructura categórica de los espacios vectoriales para representar árboles. Es decir, en la teoría de conjuntos ordinaria, un árbol (de cierta altura fija) es una unión disjunta anidada de productos cartesianos.

Sin embargo, los espacios vectoriales también tienen sumas y productos directos, por lo que también puede representar un árbol como elemento de un espacio vectorial adecuado. Además, los productos directos y las sumas directas coinciden para los espacios vectoriales, es decir, tienen la misma representación. Esto abre la puerta a implementaciones paralelas: dado que las representaciones físicas son las mismas, se pueden eliminar muchas ramificaciones y persecuciones de punteros.

También explica por qué el análisis del flujo de datos es de tiempo cúbico: ¡está computando vectores propios!

En las redes, los enrutadores usan TCAM (memorias ternarias direccionables por contenido; en otras palabras, memoria direccionable por contenido con un bit de no me importa) para clasificar el tráfico. Las entradas en un TCAM a menudo son reglas de coincidencia de prefijos multidimensionales: por ejemplo, (101 *, 11 *, 0 *) coincide con cualquier paquete donde el primer campo de encabezado comienza con 101 y el segundo campo de encabezado comienza con 11 (y etc.) Si un paquete no coincide con la primera regla, pasa a la segunda, y así sucesivamente hasta que se encuentre una regla coincidente.

$d$$R^{d+1}$$d+1$$R^{d+1}$$d$$d+1$

Para las personas de redes, esta interpretación es útil para comprender lo que hace un conjunto específico de reglas. Para los teóricos, hay otros usos interesantes. Según los algoritmos para la clasificación de paquetes de Gupta y McKeown, la interpretación geométrica nos permitió establecer rápidamente límites inferiores y superiores para el problema de la clasificación de paquetes. Sé que el trabajo en la minimización de reglas TCAM (encontrar el menor número de reglas que conserva la semántica) también se ha beneficiado de un enfoque geométrico. Hay toneladas de referencias que podría dar para esto, pero la que puede ser de mayor utilidad para usted es el documento SODA 2007 de Applegate, et al. Comprimiendo imágenes rectilíneas y minimizando las listas de control de acceso. Demuestran que minimizar una variante más general de las reglas de coincidencia de prefijos anteriores es NP-hard, y lo conectan (nuevamente) a imágenes bonitas de rectángulos para resolver el problema.

Me sorprende que nadie haya dicho el Algoritmo Euclidiano por encontrar el mayor factor común entre dos números. Puede resolver el problema dibujando un rectángulo axb, luego subdividir el rectángulo por el cuadrado creado por el lado más pequeño, repetir para el rectángulo sobrante, seguir repitiendo para los rectángulos sobrantes hasta que encuentre un cuadrado que pueda dividir uniformemente el rectángulo restante (ver gif animado en la página Algoritmo euclidiano).

Una manera bastante elegante de tratar de descubrir cómo funciona la cosa, en mi opinión.

Probablemente también hay demasiados ejemplos para enumerar, pero un ejemplo clásico (es resaltado por Aigner y Ziegler como " Prueba del libro ") es el uso de Lovász de una representación geométrica para resolver un problema en la capacidad de Shannon. Aunque la prueba se publicó en 1979 y resolvió una pregunta abierta de 1956, esto sigue siendo lo último.

Relación de códigos de corrección de errores con celosías, empaquetamiento de esferas, etc. (por ejemplo, libro de Conway y Sloane). Sin embargo, la relación es tan fuerte que no está del todo claro si debo llamar a los códigos de corrección de errores "completamente no geométricos" después de eso ...

Las técnicas de reducción de celosía, como LLL o PSLQ , son altamente geométricas y resuelven problemas de teoría de números puros, como la aproximación lineal de diofantina y la detección de relaciones de enteros.

$\mathbb{Z}$$\mathbb{Z}$

A Gerard Salton se le ocurrió la idea de usar el coseno del ángulo entre vectores (similitud de coseno) para los sistemas de recuperación de información. Esto se usó para calcular el término frecuencia-frecuencia de documento inversa. Considero que este es el predecesor de los motores de búsqueda modernos. Ver también Modelo de espacio vectorial.

$k$$k$

Por supuesto, la prueba es más topológica que geométrica, pero en baja dimensión tiene una imagen geométrica clara. Que yo sepa, no existe una prueba puramente combinatoria (es decir, una prueba que pueda explicar a una persona que se niega a escuchar algo sobre topología).

El papel de las curvas de relleno de espacio en las bases de datos y la optimización: http://people.csail.mit.edu/jaffer/Geometry/MDSFC

La máquina de vectores de soporte en el aprendizaje automático probablemente califica.

Existen técnicas de geometría computacional para resolver la programación lineal. Geometría computacional: los algoritmos y las aplicaciones tienen un capítulo agradable y simple sobre eso.

Una integral definida de una función se puede representar como el área firmada de la región limitada por su gráfico.