Exemples où la compréhension de la géométrie était utile pour résoudre quelque chose de complètement non géométrique

L'une des bonnes choses d'avoir évolué dans un univers à trois dimensions spatiales est que nous avons développé des compétences en résolution de problèmes concernant les objets dans l'espace. Ainsi, par exemple, nous pouvons considérer un triplet de nombres comme un point en 3-d et donc le calcul de triplets de nombres comme un calcul de points en 3-d, qui peut ensuite être résolu en utilisant notre intuition sur l'espace. Cela semble suggérer qu'il devrait parfois être possible de résoudre un problème complètement non géométrique en utilisant des techniques de géométrie. Quelqu'un connaît-il de tels exemples?

Bien sûr, les termes «géométrique» et «non géométrique» sont légèrement vagues ici. On peut affirmer que tout problème géométrique est en fait non géométrique si vous remplacez tous les points par leurs coordonnées. Mais intuitivement, la définition est claire. Disons simplement que nous appelons quelque chose de géométrique si nous envisageons d'envoyer un article à ce sujet à SoCG.

Quelques exemples supplémentaires:

Sleator, Thurston et Tarjan ont utilisé une représentation géométrique des arbres comme partitions de polygones et une géométrie hyperbolique pour prouver les limites inférieures de la rotation des arbres binaires . (De plus, je crois que l' histoire d'un arbre de recherche binaire dynamique peut être représentée comme une tétraédrique.)

La réduction de l'ancêtre le moins commun pour couvrir des requêtes minimales , due à Berkman et Vishkin, relie un problème de structures de données sur les arbres à un problème sans doute géométrique. (et merci pour l'article David)

La réduction d'un problème d'ordonnancement à un ensemble indépendant de poids maximum de rectangles parallèles à l'axe [1] ou la réduction d'un problème d'ordonnancement différent à la couverture d'ensemble géométrique [2] pourrait être qualifiée.

La réduction du plus grand problème de sous-séquence commun à la recherche de couches de maxima est bien connue (ce qui signifie que je suis trop paresseux pour rechercher qui y a réellement pensé).

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

[2] Nikhil Bansal, Kirk Pruhs. The Geometry of Scheduling, FOCS 2010.

[modifier plus tard] Quelques autres cas où une vue "géométrique" semblait surprenante (bien que les normes de "soumission à SoCG" ou de "quelque chose à visualiser" ne soient probablement pas respectées):

topologie algébrique appliquée aux bornes inférieures pour l'informatique distribuée

incorporer la calculabilité dans la dimension de Hausdorff

définir une notion de distance pour les groupes, puis le volume, puis la croissance du volume en fonction de la distance, puis utiliser la "croissance polynomiale"

Bien sûr, une bien meilleure réponse que la précédente est l'utilisation de la théorie de l'intégration métrique pour résoudre la coupe la plus clairsemée. Une étape clé dans la solution du problème de coupe le plus clairsem a été la réalisation qu'il pourrait être approché en trouvant une bonne intégration d'une métrique générale dans un $\ell_1$ espace normalisé .

Celles-ci ont également été mentionnées ailleurs, mais un exemple que j'aime est le suivant: le tri avec des informations partielles est le problème de trouver une extension linéaire fixe inconnue d'un poset, étant donné le poset et d'utiliser un nombre de requêtes de comparaison aussi proche que possible de la théorie de l'information borne inférieure (il s'agit simplement d'un tri lorsque le nombre de comparaisons est la mesure critique de complexité et que certaines comparaisons sont données gratuitement). L'existence de stratégies de comparaison optimales (jusqu'à une constante) a été prouvée par Saks et Kahn en utilisant les propriétés du polytope d'ordre, un polytope spécial associé à un poset (vous pouvez trouver une grande exposition dans le livre de Matousek Lectures on Discrete Geometry). Le premier algorithme de temps polynomial (par Kahn et Kim) qui calcule une stratégie de comparaison optimale (jusqu'à une constante) a de nouveau utilisé les propriétés du polytope d'ordre ainsi que le polytope d'ensemble stable du graphique d'incomparabilité du poset d'entrée.

Il y a un article relativement récent de Demaine et al qui utilise une représentation géométrique des arbres de recherche binaires pour faire avancer l'état de l'art sur l'optimalité dynamique. Je suis un peu vague ici car ils ne résolvent pas la conjecture DO: mais ils renforcent certaines limites et donnent de nouvelles perspectives qui semblent provenir de la formulation géométrique.

Je ne pense pas qu'il y ait d'exemples de telles choses. Sauf pour la programmation linéaire, la programmation semi-définie, les nombres complexes, les grandes fractions d'apprentissage automatique, etc. La vraie question est http://www.youtube.com/watch?v=ExWfh6sGyso .

L'année dernière, il y avait un bon article au POPL, EigenCFA: Accelerating flow analyse with GPUs , qui représentait les termes lambda sous forme de matrices, puis utilisait des GPU pour effectuer rapidement une analyse de flux de données sur eux.

Le document ne l'a pas précisé explicitement, mais ce qu'ils faisaient essentiellement était d'exploiter la structure catégorielle des espaces vectoriels pour représenter les arbres. Autrement dit, dans la théorie des ensembles ordinaires, un arbre (d'une certaine hauteur fixe) est une union disjointe imbriquée de produits cartésiens.

Cependant, les espaces vectoriels ont également des produits et des sommes directs, de sorte que vous pouvez également représenter un arbre comme élément d'un espace vectoriel approprié. De plus, les produits directs et les sommes directes coïncident pour les espaces vectoriels - c'est-à-dire qu'ils ont la même représentation. Cela ouvre la porte à des implémentations parallèles: puisque les représentations physiques sont les mêmes, beaucoup de branchements et de pointeurs peuvent être éliminés.

Cela explique également pourquoi l'analyse de flux de données est cubique: c'est le calcul de vecteurs propres!

Dans la mise en réseau, les routeurs utilisent des TCAM (mémoires ternaires adressables au contenu - en d'autres termes, la mémoire adressable au contenu avec un bit indifférent) pour classer le trafic. Les entrées dans un TCAM sont souvent des règles de correspondance de préfixe multidimensionnelles: par exemple, (101 *, 11 *, 0 *) correspond à tout paquet où le premier champ d'en-tête commence par 101 et le second champ d'en-tête commence par 11 (et etc.) Si un paquet ne correspond pas à la première règle, il passe à la seconde, et ainsi de suite jusqu'à ce qu'une règle correspondante soit trouvée.

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

Pour les personnes en réseau, cette interprétation est utile pour comprendre ce que fait un ensemble spécifique de règles. Pour les théoriciens, il existe d'autres utilisations intéressantes. Selon Algorithms for Packet Classification de Gupta et McKeown, l'interprétation géométrique nous a permis d'établir rapidement des limites inférieures et supérieures pour le problème de la classification des paquets. Je sais que les travaux sur la minimisation des règles TCAM (trouver le plus petit nombre de règles qui préserve la sémantique) ont également bénéficié d'une approche géométrique. Il y a des tonnes de références que je pourrais donner à ce sujet, mais celle qui peut être la plus utile pour vous est le document SODA 2007 d'Applegate et al.Compression d' images rectilignes et minimisation des listes de contrôle d'accès. Ils prouvent que minimiser une variante plus générale des règles de correspondance des préfixes ci-dessus est NP-difficile, et le connecter (encore) à de jolies images de rectangles pour résoudre le problème!

Je suis surpris que personne n'ait dit l' algorithme euclidien pour trouver le plus grand facteur commun entre deux nombres. Vous pouvez résoudre le problème en dessinant un rectangle axb, puis sous-divisez le rectangle par le carré créé par le plus petit côté, répétez l'opération pour le rectangle restant, continuez à répéter pour les rectangles restants jusqu'à ce que vous trouviez un carré qui peut diviser également un rectangle restant (voir gif animé sur la page Algorithme Euclidien).

Une façon assez élégante d'essayer de comprendre comment ça fonctionne, OMI.

Il y a probablement trop, trop d'exemples à énumérer, mais un exemple classique (il est mis en évidence par Aigner et Ziegler comme une " preuve du livre ") est l'utilisation par Lovász d'une représentation géométrique pour résoudre un problème dans la capacité de Shannon. Bien que la preuve ait été publiée en 1979 et ait résolu une question ouverte à partir de 1956, elle reste à la pointe de la technologie.

Relation des codes de correction d'erreur avec les treillis, l'emballage de sphères, etc. (par exemple, livre Conway et Sloane). Pourtant, la relation est si forte, qu'elle n'est pas tout à fait claire, si je devais appeler les codes de correction d'erreur «complètement non géométriques» après cela ...

Les techniques de réduction de réseau, telles que LLL ou PSLQ , sont hautement géométriques et résolvent des problèmes de théorie des nombres purs, tels que l'approximation diophantienne linéaire et la détection de relations entières.

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

Gerard Salton a eu l'idée d'utiliser le cosinus de l'angle entre les vecteurs (similitude cosinus) pour les systèmes de recherche d'informations. Il a été utilisé pour calculer la fréquence du terme – fréquence du document inverse. Je considère que c'est le prédécesseur des moteurs de recherche modernes. Voir aussi Modèle d'espace vectoriel.

$k$$k$ coupes. Pour le prouver, placez le collier sur la courbe des moments et utilisez une variante du théorème du sandwich au jambon (voir un joli livre "Utilisation du théorème de Borsuk – Ulam" de Jiří Matoušek).

Bien sûr, la preuve est plus topologique que géométrique, mais en faible dimension elle a une image géométrique claire. À ma connaissance, il n'existe aucune preuve purement combinatoire (c'est-à-dire une preuve que vous pouvez expliquer à une personne qui refuse d'entendre quoi que ce soit sur la topologie).

Le rôle des courbes de remplissage d'espace dans les bases de données et l'optimisation: http://people.csail.mit.edu/jaffer/Geometry/MDSFC

La prise en charge de la machine vectorielle dans l'apprentissage automatique est probablement qualifiée.

Il existe des techniques de géométrie computationnelle pour résoudre la programmation linéaire. Géométrie informatique: les algorithmes et les applications ont un chapitre simple et agréable à ce sujet.

Une intégrale définie d'une fonction peut être représentée comme la zone signée de la région délimitée par son graphique.