Exemplos em que o insight da geometria foi útil para resolver algo completamente não-geométrico

Uma das coisas boas de ter evoluído em um universo com três dimensões espaciais é que desenvolvemos habilidades de resolução de problemas referentes a objetos no espaço. Assim, por exemplo, podemos pensar em um trigêmeo de números como um ponto em 3-d e, portanto, computação sobre trigêmeos de números como computação sobre pontos em 3-d, que podem ser resolvidos usando nossa intuição sobre o espaço. Isso parece sugerir que às vezes seja possível resolver um problema completamente não geométrico usando técnicas da geometria. Alguém conhece esses exemplos?

Obviamente, os termos 'geométrico' e 'não geométrico' são um pouco vagos aqui. Pode-se argumentar que qualquer problema geométrico não é realmente geométrico se você substituir todos os pontos por suas coordenadas. Mas intuitivamente, a definição é clara. Digamos que chamamos de algo geométrico se considerarmos enviar um artigo sobre isso para o SoCG.

Mais alguns exemplos:

Sleator, Thurston e Tarjan usaram uma representação geométrica de árvores como partições de polígonos e geometria hiperbólica, para provar limites inferiores para rotação binária de árvores . (Além disso, acredito que o histórico de uma árvore de pesquisa binária dinâmica pode ser representado como uma tetraedro.)

A redução do ancestral menos comum para o alcance de consultas mínimas , devido a Berkman e Vishkin, relaciona um problema de estruturas de dados em árvores a um problema geométrico indiscutível. (e obrigado pelo artigo David)

A redução de um problema de programação para o conjunto independente de peso máximo de retângulos paralelos ao eixo [1] ou a redução de um problema de programação diferente para a cobertura do conjunto geométrico [2] pode se qualificar.

A redução do maior problema de subsequência comum para encontrar camadas de máximos é bem conhecida (ou seja, estou com preguiça de procurar quem realmente pensou nisso).

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

[2] Nikhil Bansal, Kirk Pruhs. A geometria da programação, FOCS 2010.

[editar mais tarde] Mais alguns casos em que uma visão "geométrica" ​​parecia surpreendente (embora os padrões "submissão ao SoCG" ou "faça algo para visualizar" provavelmente não sejam atendidos):

topologia algébrica aplicada a limites inferiores para computação distribuída

incorporando computabilidade na dimensão Hausdorff

definindo uma noção de distância para grupos, depois volume e, em seguida, crescimento de volume em função da distância, usando "crescimento polinomial"

É claro que uma resposta muito melhor do que a anterior é o uso da teoria de incorporação métrica para resolver cortes mais esparsos. Um passo importante na solução do problema de corte mais esparso foi a percepção de que ele poderia ser aproximado, encontrando uma boa incorporação de uma métrica geral em um espaço $\ell_1$ .

Eles também foram mencionados em outro lugar, mas um exemplo que eu gosto é: classificar com informações parciais é o problema de encontrar uma extensão linear desconhecida fixa de um poset, dado o poset e usar o número de consultas de comparação o mais próximo possível da teoria da informação limite inferior (isso é apenas uma classificação quando o número de comparações é a medida da complexidade crítica e algumas comparações são feitas de graça). A existência de estratégias de comparação ótimas (até constantes) foi comprovada por Saks e Kahn, usando as propriedades do pólipo de ordem, um polítopo especial associado a um poset (você pode encontrar uma excelente exposição no livro Palestras sobre geometria discreta de Matousek). O primeiro algoritmo de tempo polinomial (de Kahn e Kim) que calcula uma estratégia de comparação ótima (até constante) novamente usou as propriedades do polítopo da ordem, bem como o polítopo estável do gráfico de incomparabilidade do poset de entrada.

Existe um artigo relativamente recente de Demaine et al. Que usa uma representação geométrica de árvores de busca binária para avançar o estado da arte em otimização dinâmica. Estou sendo um pouco vago aqui, porque eles não resolvem a conjectura de DO: mas reforçam alguns limites e dão novas idéias que parecem vir da formulação geométrica.

Eu não acho que existem exemplos de tais coisas. Exceto para programação linear, programação semi-definida, números complexos, grandes frações de aprendizado de máquina etc. A verdadeira questão é http://www.youtube.com/watch?v=ExWfh6sGyso .

No ano passado, houve um bom artigo na POPL, EigenCFA: Accelerating flow analysis with GPUs , que representava termos lambda como matrizes e depois usava GPUs para executar rapidamente análises de fluxo de dados nelas.

O artigo não apontou isso explicitamente, mas o que eles estavam basicamente fazendo era explorar a estrutura categórica dos espaços vetoriais para representar árvores. Ou seja, na teoria comum dos conjuntos, uma árvore (de certa altura fixa) é uma união aninhada e aninhada de produtos cartesianos.

No entanto, os espaços vetoriais também possuem produtos e somas diretos, para que você possa representar uma árvore como um elemento de um espaço vetorial adequado. Além disso, produtos diretos e somas diretas coincidem com espaços vetoriais - ou seja, eles têm a mesma representação. Isso abre as portas para implementações paralelas: como as representações físicas são as mesmas, muitas ramificações e perseguições por ponteiros podem ser eliminadas.

Também explica por que a análise do fluxo de dados é em tempo cúbico: está computando vetores próprios!

Na rede, os roteadores usam TCAMs (memórias ternárias endereçáveis ​​ao conteúdo - em outras palavras, memória endereçável ao conteúdo com um pouco de importância) para classificar o tráfego. As entradas em um TCAM geralmente são regras multidimensionais de correspondência de prefixo: por exemplo, (101 *, 11 *, 0 *) corresponde a qualquer pacote em que o primeiro campo de cabeçalho comece com 101 e o segundo campo de cabeçalho comece com 11 (e etc.) um pacote não corresponde à primeira regra, continua com a segunda e assim sucessivamente até que uma regra correspondente seja encontrada.

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

Para pessoas que trabalham em rede, essa interpretação é útil para entender o que um conjunto específico de regras faz. Para os teóricos, existem outros usos interessantes. De acordo com Algorithms for Packet Classification de Gupta e McKeown, a interpretação geométrica nos permitiu estabelecer rapidamente limites inferiores e superiores para o problema de classificação de pacotes. Sei que o trabalho sobre a minimização de regras do TCAM (encontrar o menor número de regras que preserva a semântica) também se beneficiou de uma abordagem geométrica. Há muitas referências que eu poderia dar para isso, mas a que pode ser mais útil para você é o artigo SODA 2007 da Applegate, et al., Compactando imagens retilíneas e minimizando as listas de controle de acesso. Eles provam que minimizar uma variante mais geral das regras de correspondência de prefixo acima é difícil para o NP e conectam-no (novamente) a imagens bonitas de retângulos para resolver o problema!

Estou surpreso que ninguém tenha dito o algoritmo euclidiano por encontrar o maior fator comum entre dois números. Você pode lidar com o problema desenhando um retângulo axb e, em seguida, subdividir o retângulo pelo quadrado criado pelo lado menor, repetir para o retângulo restante, continuar repetindo pelos retângulos restantes até encontrar um quadrado que possa dividir igualmente o retângulo restante (consulte gif animado na página Algoritmo Euclidiano).

Maneira bastante elegante de tentar descobrir como as coisas funcionam, IMO.

Provavelmente, existem muitos exemplos para listar, mas um exemplo clássico (destacado por Aigner e Ziegler como uma " Prova do Livro ") é o uso por Lovász de uma representação geométrica para resolver um problema na capacidade de Shannon. Embora a prova tenha sido publicada em 1979 e tenha resolvido uma questão em aberto em 1956, isso continua sendo o estado da arte.

Relação de códigos de correção de erros com reticulados, empacotamento de esferas etc. (por exemplo, livro de Conway e Sloane). No entanto, a relação é tão forte que não fica claro se devo chamar os códigos de correção de erros "completamente não geométricos" depois disso ...

Técnicas de redução de treliça , como LLL ou PSLQ , são altamente geométricas e resolvem problemas da teoria dos números puros, como aproximação linear diofantina e detecção de relação de número inteiro.

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

Gerard Salton surgiu com essa idéia de usar o cosseno do ângulo entre vetores (semelhança de cosseno) para sistemas de recuperação de informações. Isso foi usado para calcular frequência do termo - frequência inversa do documento. Considero que este é o antecessor dos motores de busca modernos. Veja também Modelo de espaço vetorial.

$k$$k$

Obviamente, a prova é mais topológica do que geométrica, mas em baixa dimensão, possui uma imagem geométrica clara. Que eu saiba, não existe prova puramente combinatória (isto é, uma prova que você possa explicar a uma pessoa que se recusa a ouvir algo sobre topologia).

O papel das curvas de preenchimento de espaço nos bancos de dados e na otimização: http://people.csail.mit.edu/jaffer/Geometry/MDSFC

A máquina de vetores de suporte no aprendizado de máquina provavelmente se qualifica.

Existem técnicas de geometria computacional para resolver programação linear. Geometria computacional: algoritmos e aplicativos tem um capítulo simples e agradável sobre isso.

Um Integral Definido de uma função pode ser representado como a área assinada da região delimitada por seu gráfico.