Comments on Sections du diagramme de Voronoï du réseau E₈

jonas (2020-02-11T16:55:31Z)

Ruxor: I just found a research article from 1996 answering your question <URL: http://www.madore.org/cgi-bin/comment.pl/showcomments?href=http%3a%2f%2fwww.madore.org%2f~david%2fweblog%2f2017-04.html%23d.2017-04-09.2433#comment-23507 >. The abstract calls it a “long-standing question in stochastic geometry”. I suspect that's an exaggeration.

S. N. Chiu; R. Van De Weygaert; D. Stoyan, “The Sectional Poisson Voronoi Tessellation Is Not a Voronoi Tessellation”, (1996-06) Advances in Applied Probability vol. 28 no. 2 pp. 356-367, abstract at <URL: https://www.jstor.org/stable/1428061 >

Ruxor (2017-07-13T11:24:30Z)

@jonas: Your argument showing that not every d-dimensional cross-section of an n-dimensional Voronoi diagram is a d-dimensional Voronoi diagram is very elegant, thank you. As for the procedure consisting of taking an n-dimensional Poisson process and replacing the n−d last coordinates by the square root of the sum of their squares, I would imagine it has a classical name, but I can't find a way to Google it; it is vaguely reminiscent of the procedure by which the χ² (chi-squared) distribution is constructed, so you would then be trying to detect the number of "degrees of freedom". Also interesting is the question of whether there is a limit to this, a kind of ∞-random-Voronoi diagram which, when cut to any number of dimensions, still gives you a process of the same kind. (I know very little about probability, so I don't even know how to formulate the question properly.)

jonas (2017-07-11T01:25:54Z)

> Maybe there is a theorem saying that a d-dimensional section of the Voronoi diagram of an n-dimensional Poisson process is the same (up to a constant density factor) as that of a d-dimensional Poisson process — I don't know, but it wouldn't surprise me too much.

No, there isn't.

If you consider a polygon in the d-dimensional Voronoi diagram, and flip all its neighboring polygons into it by mirroring them on the shared side, the mirror images will have an intersection point. In the d-dimensional section of the n-dimensional process (where d<n), you can find counterexamples: large polygons with two small neighboring polygons, the latter ones far away from each other. You can even find such counterexamples by naked eye on the images I posted. Thus, you can recognize that a tessellation is not a d-dimensional Voronoi diagram in a very strong sense. (Clearly in the Poisson process case, you can find such a strong proof with positive probability if you look at just a fixed-size square window of the tessellation, and the probability tends to 1 as the window increases.)

In the other dimension, you can't find such a strong proof, since the Voronoi diagram of any set of points in d dimensions is also the section Voronoi diagram of a set of points in n dimensions in very special configuration. However, if d=2 and you choose the points in a general configuration, then the Voronoi diagram of a 2-dimensional point set satisfies more algebraic equalities than the planar section of the Voronoi diagram of an n-dimensional point set. Specifically, suppose you examine a diagram of the former kind. If you are given two adjacent vertexes of a polygon in the diagram and the five lines incident on these (considered as lines, not segments), then you can compute the point that was the seed of that polygon. If you are given three adjacent vertexes of a polygon and the seven or six lines incident on these, then you can compute the center in two independent ways, and this results in an algebraic equality that the first kind of diagram will satisfy but the second one in general won't. If you know the coordinates of the tessellation to infinite precision, then this gives you a proof in a somewhat weaker sense that what you're looking at is indeed not a planar section of an n-dimensional random Voronoi diagram. Again even if you're looking at a square window, you will find such a proof with positive probability, and the probability tends to 1 as the window size grows. (Note though that even the planar section of an n-dimensional diagram will satisfy more algebraic equations than a general tessellation of the plane to polygons.)

What I don't know is how to distinguish the 2-planar section of Voronoi diagram of an n-dimensional Poisson process for different values of n where 2<n. I can't seem to tell apart by naked eye.

I think you can't distinguish them for certain in the above weaker sense. To see this, assume you are projecting to the plane {(0,0,x_2,…)}, take the Poisson process in n dimensions where 3<n, and construct a new 3-dimensional point set by transforming each point (x_0,x_1,x_2,…) to (x_0,x_1,y) where y^2=x_2^2+…+x_{n-1}^2 and sgn(y)=sgn(x_2). The planar section of the Voronoi diagram of the old and the new point set is identical. The new point set is a 3-dimensional Poisson process, but with a non-uniform density. The density around (x_0,x_1,y) is proportional to y^{n-3}. This implies that the new point set looks sort of like an ordinary uniform Poisson process on 3 dimensions, and with some handwaving I think the corresponding Voronoi diagrams look similar too.

I suspect it's still possible to distinguish the diagrams for any two different values of n in a statistical manner, even after appropriate scaling. I don't have an argument to support this though.

Fab (2017-04-16T19:29:57Z)

Merci beaucoup pour ton aide David !
Il est probable que je revienne vers toi pour un ou deux conseils !

Ruxor (2017-04-16T16:13:43Z)

@Fab: Bon, tes idées sont intéressantes, mais je crois que là je vais vraiment te laisser les programmer toi-même, ne serait-ce que parce que je commence à en avoir assez d'avoir soixante versions du programme dans tous les coins, et je crois qu'il vaut mieux que tu expérimentes toi-même pour savoir ce que tu veux exactement.

Le code source des programmes que j'ai utilisés est <URL: ftp://ftp.madore.org/pub/madore/misc/e8voronoi.c > pour la version qui colorie comme je faisais initialement et <URL: ftp://ftp.madore.org/pub/madore/misc/e8voronoi-gray.c > pour la version qui fait des teintes de gris selon la distance euclidienne. Si tu as un Linux sous la main, ça doit fonctionner sans aucun problème : j'ai indiqué la ligne de commande pour la compilation en commentaire au début, tu peux rajouter des choses comme `-DNBTHREADS=4` si ton processeur n'a que quatre cœurs ou `-DPIC_WIDTH=1024 -DPIC_HEIGHT=768` si tu veux changer la taille de l'image et peut-être `-DNBFRAMES=1` si tu veux ne produire qu'une seule image à fins de test ; ensuite il faut juste avoir installé ImageMagick pour le programme `convert`, qui me sert à convertir du PPM ou PGM en PNG, on lance le programme, et il fabrique des images ayant des noms comme `frame0000.png` jusqu'à `frame1199.png` par défaut.

Si ça marche, ça doit être quand même facile à comprendre et à modifier, tu peux ignorer tout ce qui parle du lancement des threads, tu peux prendre les fonctions comme `uniform()`, `gaussian()` et `gram_schmidt()` comme des boîtes noires, et sans doute même `find_closest_e8()`, le bout vraiment utile est autour du commentaire "COMPUTATION IS HERE" (juste avant, il remplit le tableau v avec les coordonnés du point, la ligne en question calcule le point de réseau le plus proche et le stocke dans r, et la ligne fprintf qui suit écrit les coordonnées RGB entre 0 et 255 : le format PPM/P3 est complètement trivial, on écrit juste les trois coordonnées de chaque point séparées par des blancs, ou une seule pour le format PGM/P2, cf. <URL: http://en.wikipedia.org/wiki/Netpbm_format >). Je pense que même sans connaître grand-chose à la programmation, tu dois arriver à en faire ce que tu veux.

Si tu veux, je te donne une ligne de commande ffmpeg pour convertir les frames en vidéo (par exemple pour la mettre sur YouTube).

Pour ce qui est de trouver des espaces de dimension k>2 avec des symétries intéressantes, je n'ai pas les idées aussi claires que je voudrais, mais je crois qu'on ne peut pas faire grand-chose. Pour trouver un plan ayant beaucoup de symétrie, ce qu'on fait est qu'on trouve un élément d'ordre élevé dans le groupe de Weyl du système de racines, et le plan est donné essentiellement par ses vecteurs-propres (enfin, leur partie réelle et imaginaire, ou quelque chose comme ça), un élément de Coxeter étant un élément du plus grand ordre possible dans le groupe de Weyl et un plan correspondant s'appelle plan de Coxeter (ou plan de Petrie). Pour faire des choses analogues en dimension plus grande que 2, il faudrait trouver non pas des sous-groupes cycliques du groupe de Weyl mais des sous-groupes isomorphes à des groupes de Coxeter pour une dimension k>2 plus petite que le système tout entier ; l'ennui, c'est que pour k>2, il n'y a pas tant de groupes de Coxeter que ça (et je n'ai même pas les idées claires sur la question de savoir si un sous-groupe d'un groupe de Weyl/Coxeter qui est abstraitement un groupe de Coxeter de rang k est réalisable par des isométries sur un sous-espace de dimension k). Après, ça, bien sûr, c'est si tu veux une symétrie complète sur les k dimensions : mais peut-être qu'on ne veut pas vraiment en demander autant, peut-être qu'on peut chercher, par exemple, deux plans de Coxeter orthogonaux, mais là non plus je n'ai pas les idées super claires.

Fab (2017-04-16T10:38:10Z)

Deux stupidités dans ce que j'ai raconté (je dois décidément faire des dessins pour y voir quelque-chose) mais je pense que tu m'auras corrigé : le point Pi pour le calcul de la composante de couleur i relative à l'axe Oi, doit en fait être le projeté orthogonal de P (point du réseau) sur l'espace somme E+Oi. D'une part.
Et d'autre part, si on veut que la couleur composée représente une distance (dans le sens général du terme) on ne peut pas prendre (MP1,MP2,MP3), il faut prendre aussi en compte le sous-espace S supplémentaire de E+C. Je note H le projeté orthogonal de P sur S. On a alors MP^2 = MH^2 + MP1^2 + MP2^2 + MP3^2.

Reste à savoir comment gérer ce machin du fait que les quatre termes sont variables et qu'on ne dispose que de trois composantes couleur. Répartir la part MH^2 de manière équitable sur les composantes RGB (je dois y aller je réfléchirai à ça plus tard) ou ne choisir que deux axes pour les "dimensions couleur" (avec du coup un système plus adéquat que le RGB, qui prendrait en compte le rôle inégal que joue H au regard des deux autres projetés…) ?

Fab (2017-04-16T00:25:09Z)

Ah oui, effectivement je ne suis pas déçu non plus des vidéos.
Mais je continue avec mes caprices, tu permets ? ;) (certes, tu fais de toute façon ce tu veux) : pourquoi ne pas combiner la quantité d'information que donnent la couleur (ou de la bichromie qui est ptr un compromis intéressant aussi) avec la beauté esthétique du dégradé des distances (qui ajoute de l'info en soit aussi d'ailleurs) ? Pour le coup, ça devrait être encore plus zouli !

J'ai vérifié, c'est possible mais je n'ai peut-être pas été très clair (ou tu as jugé que ça n'apporterait rien de plus ?) : donnés deux 3-sous-espaces E (d'axes orth. Ox, Oy et Ot) et C (d'axes orth. Or, Og, Ob) de R^8 en somme directe, notons P1, P2, P3 les projetés orthogonaux d'un point quelconque P sur les axes Or, Og, Ob. Alors à tout point M de E (affichage), si P est son plus proche voisin d'E8, il suffit d'associer à M la couleur de composantes R=MP1, G=MP2, B=MP3.

Et esthétiquement, je prendrais plutôt la distance que son carré même si l'effet "bulles de savon" n'est pas mal du tout, pour deux raisons : pour mieux "faire le focus" sur les points du réseau qui sont proches. Et pour avoir des résultats avec un peu plus de contraste (là c'est plutôt de la spéculation). Bon, peut-être aussi, j'avoue, pour une forme de satisfaction intellectuelle à avoir un truc bien linéaire et pas une sorte d'homéomorphisme sur l'espace des couleurs…

Et aussi : est-ce qu'il serait intéressant de calculer des images ou vidéos contenant des plans de Coxeter dont l'une des directions (ou les deux) ne sont celles d'affichage mais seraient dans les couleurs ?

Argh, je commence sérieusement à avoir envie de me plonger dans la programmation… Si tu m'envoie bouler gentiment, ce serait peut-être un mal pour un bien :D, je vais m'y mettre…

Je pensais sinon à quelque-chose, existe-t-il des k-espaces de Coxeter intéressants (pas trop triviaux) pour k>2 ? J'imagine que oui mais que tu n'en as pas parlé parce-qu'il sont super compliqués à calculer ? Et y a-t-il une relation d'inclusion entre eux (lorsqu'on les indexe avec la dimension k) ? (C'est sûr que si les 3-espaces de Coxeter ne contiennent pas de plan de Coxeter, l'intérêt d'une telle représentation en 2D+ temps est peut-être plus limité…)

Aller Ruxor, encore une dimension d'affichage (z) et une « dimension musicale » (cf. ton billet suivant [#]) et on a une représentation complète en hologramme musical d'E8 ! Un petit effort !

# Ton billet suivant, mais pas seulement ! j'ai eu une petite insomnie la dernière nuit (et donc *avant* d'avoir découvert ton billet qui suit !) _ cet E8 et son diagramme de Voronoï m'obsèdent, vraiment _ où j'ai médité sur la question d'un type de représentation musicale d'image, si si. Et j'ai pensé moi aussi aux fonctions quasi-périodiques (sans vraiment avoir une idée précise de ce que c'est) du fait que là, en l'occurrence, il doit effectivement y avoir une forme de quasi-périodicité de manière presque sûre lorsqu'un plan est tiré aléatoirement. Je crois vraiment qu'il y a là un terrain de jeu assez excitant !

Ruxor (2017-04-14T21:45:58Z)

@Fab: Effectivement, la suggestion de tracer selon la distance était excellente, et je trouve les vidéos magnifiques. Voir l'"ajout 2" que j'ai mis à la fin de mon entrée (recharger la page s'il n'apparaît pas). J'ai pris le noir pour les points du réseau et la blanc pour les trous (du coup, ce sont les points du réseau qui apparaissent visuellement comme des trous, ce qui est finalement peut-être plus logique si on pense à un diagramme de Voronoï comme des bulles de savon ou quelque chose de ce genre).

Pour ta question finale, je n'ai pas bien réfléchi, mais je pense qu'un plan de Coxeter est plutôt quelque chose qui est aussi loin que possible de contenir un sous-réseau (mais bon, je ne sais pas trop en quoi).

Fab (2017-04-14T15:20:55Z)

(Ah mais non, la distance max est 1, pas 2√2/3)
Si le plan ou 3-espace d'affichage contient des points d'E8, alors ces derniers seront blancs (pour d=0 -> 255) et le dégradé de couleur linéaire dans les "directions d'affichage" (et bidouiller le mapping du codage de couleur avec une variation rapide en d=0 permettrait éventuellement d'accentuer cet effet ponctuel ; à l'inverse avec un taux d'accroissement lent voire nul en d=0, peut-être que le visuel permet plutôt de focaliser sur les séparations entre les cellules…)

A contrario, au niveau des trous profonds on aura à l'inverse du noir mais avec un dégradé de couleur des plus lents aux voisinages de ces points. D'ailleurs aux voisinages des trous, R^8 est partitionné dans tout pleins de directions, non ? (Et dans une stratégie similaire à la précédente, implémenter une variation rapide du mapping au voisinage de d=1 et de d=2√2/3 permettrait de mieux localiser les frontières entre les cellules.)

Au fait, y a-t-il un lien entre les plans de Coxeter (ou du même genre, e.g. avec symétrie d'ordre 24) avec des plans contenant des sous-réseaux (maximaux ?) d'E8 ? Voire avec des plans contenant des trous ?

Oh dis, Ruxor, calcule-nous quelques-unes de ces images/vidéos :D

Fab (2017-04-14T12:20:35Z)

@Ruxor: Je serais tout de même curieux de voir ce que donne l'image (ou mieux, la vidéo !), avec un cadrage de quelques unités seulement (pour mieux voir ce qu'il se passe) où cette fois chaque composante couleur est calculée à partir de la distance (classique, non orientée) du projeté orthogonal du point du réseau le plus proche sur l'axe orthogonal associé (à la couleur) au plan (ou 3-espace) d'affichage, à CHAQUE point du plan (ou 3-espace) d'affichage.

À essayer avec distance nulle -> saturation max 255 ce qui ferait des pixels (resp. sombres) lorsque des points d'E8 sont proches du plan ou 3-espace d'affichage. Mais aucune chance d'avoir du rouge ou vert ou bleu pur par-contre.
À l'inverse avec distance max (2√2/3) -> 255, les points passant par le plan ou 3-espace sont noirs, image globalement moins lumineuse mais probas d’occurrence de rouge, vert ou bleu purs…

Certes le calcul d'une telle image (ou 3-espace…) sera certainement beaucoup plus long (mais pas démesurément pas, si ?) mais ça risque d'être intéressant non ? Et un vague intuition me dit que pour un plan de coxeter ou machin du genre, on pourrait avoir des visuels intéressants. Et quid des cas ou une ou plusieurs des 5 ou 6 dimensions sont alignées avec des points (voire un max de points). Selon que la ou les dimensions choisie-s sont du type XYT ou RGB. etc. etc.

Sincèrement, j'ai jeté un œil au code, et j'ai bien peur de ne pouvoir faire grand-chose moi-même… ^_^

Ruxor (2017-04-12T19:36:19Z)

@Fab: Je suis d'accord que les 3 dimensions RGB ne jouent pas le même rôle que les 2(+1) dimensions d'affichage(+temps). Principalement parce que dans ces dernières on voit vraiment tout, alors que dans les dimensions RGB on voit seulement le point de réseau le plus proche, pas ceux qui sont cachés derrière. Mais bon, c'est déjà un peu mieux que dans les 2 ou 3 dimensions restantes où on ne voit carrément rien du tout. Et sur certaines images que j'ai faites (je rappelle l'adresse de l'album complet : <URL: http://imgur.com/a/mfrM6 >), on a quand même bien l'impression qu'il se passe quelque chose (notamment une forme de périodicité) dans la composante rouge, verte ou bleue séparément. J'avoue que je n'ai moi non plus pas les idées super claires.

En tout cas, oui, mon mapping des trois directions vers les trois composantes de la couleur est linéaire (enfin, affine : le zéro correspond au gris moyen). Je sais que la distance (la vraie distance euclidienne, donc la distance selon un axe donné) ne peut jamais dépasser 1, et je fais une fonction affine de [−1;1] vers [0;255] pour calculer chaque composante.

J'ai mis le code source ici, d'ailleurs, si quelqu'un veut jouer avec : <URL: ftp://ftp.madore.org/pub/madore/misc/e8voronoi.c >.

Fab (2017-04-12T16:31:26Z)

@Ruxor: oui j'ai compris, merci ! (un dessin avec une "droite d'affichage" et deux directions orthogonales m'a définitivement convaincu… la géométrie spatiale n'a jamais été mon truc, alors en 6D…)

Par-contre, il semble que l'utilisation faite des dimensions spatiales (ou temporelle) n'est pas de la même nature que celle faite des composantes RGB puisque tu intègres ces composantes à l'image (au sens mathématique) de ta représentation aléatoire du réseau, et non pas comme des variables de l'espace de départ (que sont x, y et t pour une représentation classique en 3-espace).
Certes, il est inconcevable de représenter un modélisation de type (x,y,t,r,g,b) -> E8 alors du coup tu as modélisé une représentation (x,y,t) -> (R,G,B) _ou (E8,R,G,B) mais le résultat est le même_.

Clairement, j'ai compris que tu ne cherchais qu'une méthode de coloriage, reproductible et élégante, et c'est réussi (je suis surpris d'ailleurs que les couleurs obtenues ne soient pas toutes plus ou moins proches d'un gris-marron dégueulasse : est-ce que tes transformations distance > composante sont linéaires ?) mais du coup peut-on vraiment parler de représentation 5D ou 6D ?
J'imagine que oui puisqu'il y a bien derrière tout ça une décomposition de R8 selon 5 ou 6 axes orthogonaux, mais la "structure fonctionnelle" de ce machin m'échappe et ça m'énerve !

Ruxor (2017-04-12T15:45:41Z)

@Fab: Quand je dis "la distance entre x et y selon l'axe D", je veux dire la distance entre les projetés orthogonaux de x et y sur D (et plus exactement, la distance orientée, c'est pour ça que dans mon dernier commentaire, j'ai écrit "l'écart, positif ou négatif"). Ici, x est le point à tracer et y est le point du réseau, D est une des directions choisies pour le coloriage, et le projeté de x sur D ne change pas quand x parcourt la tranche 2D ou 3D de la cellule de Voronoï puisque D est perpendiculaire au plan (ou au 3-espace) représenté.

Fab (2017-04-12T15:25:42Z)

@Ruxor: merci pour la réponse mais euh… la distance euclidienne d entre un point M fixé de R^8 (ici un certain point du réseau mais peu importe) et un point variable du plan (resp. 3-espace) a des propriétés bien définies : elle a une nappe d'hyperboloïde (à deux nappes) pour représentation, ses lignes (resp. surfaces) de niveau sont des cercles (resp. des sphères) concentriques et son min global est atteint en le projeté orthogonal de M sur le plan considéré.

Bref la distance dont tu parles (comme toute distance euclidienne à un point définie sur un sous-espace affine) *dépend* du point considéré. Ou bien on ne parle pas de la même chose ?

Fab (2017-04-12T15:18:50Z)

@Ruxor: merci pour la réponse mais euh… la distance euclidienne d entre un point M fixé de R^8 (ici un certain point du réseau mais peu importe) et un point variable du plan (resp. 3-espace) a des propriétés bien définies : elle a une nappe d'hyperboloïde (à deux nappes) pour représentation, ses lignes (resp. surfaces) de niveau sont des cercles (resp. des sphères) concentriques et son min global est atteint en le projeté orthogonal de M sur le plan considéré.
Ou bien on parle de choses différentes ?

Ruxor (2017-04-12T12:31:06Z)

@Fab: S'agissant du choix des couleurs, d'abord, j'ai fait ça par simplicité, parce que je n'avais pas vraiment idée de comment colorier les cellules de Voronoï, je me suis d'ailleurs posé la question <URL: http://mathoverflow.net/questions/266915/chromatic-number-of-voronoi-diagrams-of-lattices > et rendu compte que je n'en avais aucune idée. Prendre trois projections orthogonales m'a semblé la façon la plus simple d'avoir une couleur reproductible et ne faisant pas intervenir de tirage aléatoire.

Les trois composantes RGB donnent la distance, ou plus exactement l'écart (positif ou négatif), selon trois directions orthogonales, entre le point considéré et la point du réseau (au centre de la cellule). La raison pour laquelle ça ne dépend pas du point considéré est que les trois directions "de couleur" sont non seulement orthogonales entre elles mais aussi orthogonales au plan d'affichage (et, s'agissant des vidéos, à la direction de parcours). Du coup, tous les points de la cellule situés dans le plan d'affichage (ou dans le 3-espace d'affichage, pour les vidéos) sont à la même distance du point central de la cellule dans les trois directions supplémentaires choisies pour la couleur. Eh oui, c'est difficile d'imaginer beaucoup de dimensions…

Je suis d'accord que ce n'est pas super parlant, mais ça permet un tout petit peu de compléter au-delà de 3 dimensions… on fait ce qu'on peut. De toute façon, je répète que mon intention initiale était surtout d'avoir une méthode simple de coloriage.

Fab (2017-04-12T09:38:58Z)

Comme quoi le fait de mettre par écrit ses interrogations permets parfois de les résoudre : oui, j'imagine que la composante en chacune des couleurs primaires représente la distance minimale au point du réseau, mais permettre un dégradé de couleurs sur le polygone (ou compromis intermédiaire pour une meilleurs visibilité, qui rendrait compte de l'emplacement du projeté orthogonal du centre de la cellule sur chaque polygone) ne donnerait-il une visualisation plus informative ?
Une représentation 2 dimensions spatiales + temps est objectivement plus riche qu'une représentation 2 dimensions spatiales + 1 couleur, non ? Je veux dire, même si on restreint la 1re sur un intervalle de temps très limité : on "voit" tout de même les cellules "ap/dis -paraître" et donc où sont les points les plus proches des centres des cellules. Même si ceci est peut-être déterminé aussi dans le 2nd type de représentation ? (ce qui resterait malgré tout très difficilement saisissable par la vue et l'intuition, non ?

Fab (2017-04-12T09:13:06Z)

Très joli travail. Je commence à me faire une idée de ce fameux réseau E8 et pourquoi son étude est si intéressante.

Juste un point que j'ai du mal à saisir est l'utilisation des couleurs que tu fais pour donner plus de "relief" à la photo du réseau. Pour les vidéos, c'est très clair, notre plan se dirige à vitesse constante dans une direction orthogonale de sorte qu'on voit quasiment les polyèdres se dessiner. C'est beau.

Et toujours d'accord, le système de décomposition RGB des couleurs permet d'étendre la photo sur trois nouvelles dimensions ok, mais je ne comprends ce que tu entends par « les composantes rouge, verte et bleue donnent la distance au point du réseau (le centre de la cellule de Voronoï) selon […] trois directions » (orthogonales au plan et orthogonales entre elles) : la distance entre le point du réseau et qui ? le point du plan considéré ? Ne devrait-il pas y avoir du coup sur chaque polygone un dégradé de couleurs qui rend compte de l'éloignement au point du réseau ? Ou alors s'agit-il de la distance minimale pour chaque polygone ?

Pas facile de voir en six dimensions T_T

Héhéhé (2017-04-12T07:26:53Z)

Je me suis permis de mettre un lien vers ta vidéo sur /r/math (<URL: https://www.reddit.com/r/math/comments/64s1mn/voronoi_cells_of_the_e8_lattice_a_random/ >).

Ruxor (2017-04-10T21:33:43Z)

@jonas: The direction of the plane section does indeed make a huge difference on what the image looks like. But the lattice itself still seems to make a difference, at least between E₈, D₈ and A₈ (the case of ℤ⁸ is too trivial), though I'm not quite sure how to describe it. (There is, of course, the question of how to scale: should we compare these lattices by using the same covolume? the same covering radius? the same packing radius?)

On the images you uploaded, I definitely can't tell dimensions apart. Maybe there is a theorem saying that a d-dimensional section of the Voronoi diagram of an n-dimensional Poisson process is the same (up to a constant density factor) as that of a d-dimensional Poisson process — I don't know, but it wouldn't surprise me too much.

And I too am inclined to believe that plane sections of the Voronoi diagram of the Leech lattice would just look like a random one. (Since decoding the Leech lattice is very tedious, I won't try anyway.)

jonas (2017-04-10T20:04:36Z)

Sure, comparing the images you get for different grids can be useful. You might consider making additional images, such as multiple random planes to make sure that the differences you see really come from the different grids, not the different planes, or trying grids that aren't quite Z^n but do decompose to direct sums of orthogonal grids of lower dimensions.

I, however, wanted to try what happens if I don't take a grid at all, but only random points in the space. I also chose random colors, not the systematic colors you took, which may make the comparison difficult. The resulting images are at <URL: http://math.bme.hu/~ambrus/pu/randvoronoi.html >. I suspect that if you trid to visualize a random section of the Voronoi cells from a high dimensional lattice, such as the 24-dimensional Leech lattice, then the periodicity would be so well hidden that it would look very similar to these random images.

Ruxor (2017-04-10T17:08:28Z)

@Ilia: Dans le cas de ℤ⁸, les différences sont complètement évidentes à l'œil nu, parce que les parois des cellules de Voronoï (lesquelles sont des cubes de côté 1) sont des hyperplans complets, pas juste des bouts d'hyperplans (ma façon de le dire n'est pas très claire, mais je suppose que tu comprends) : donc même quand on coupe avec un plan, on obtient un diagramme dont les cellules sont limitées par des droites. En fait, on obtient les composantes connexes du complémentaire de huit familles de droites parallèles régulièrement espacées. Avec ma façon de colorier, il y a aussi des effets de couleurs très nets.

Bon, j'ai eu le courage de faire les calculs pour A₈ et D₈, à la fois pour une section aléatoire et pour un plan de Coxeter, et les différences sont également assez visibles, même si elles sont plus subtiles que pour ℤ⁸ et je ne saurais pas exactement mettre le doigt dessus. J'ai mis tout ça sur <URL: http://imgur.com/a/mfrM6 >.

Ilia (2017-04-10T15:31:02Z)

Si on fait le même travail en remplaçant le réseau E8 (et ses cellules de Voronoï) par un bête réseau Z^n (soit un damier d'hypercubes), est-ce que le résultat sera sensiblement différent ? Je veux dire, y a-t-il des phénomènes qu'on voit apparaître à l'oeil nu pour le réseau E8 et qui ne se produisent pas déjà pour Z^n ?

(Bien sûr, il y a cette symétrie d'ordre 30. Mais pour le réseau Z^n, on peut sûrement aussi trouver des centres de symétrie, même si l'ordre n'est pas le même - typiquement, il doit être facile de trouver une symétrie d'ordre n.)

Fred le marin (2017-04-10T14:42:14Z)

"Color our world blackened"

En ce qui concerne la quasi-périodicité, peut-être établir un (faible) lien avec les fonctions fuchsiennes (automorphes) chères à Poincaré ?
Je dis ça un peu au hasard, mais il y a bien, à la base (et d'après ce que j'ai compris), une couverture (un réseau) du plan par des parallélogrammes [deux périodes, en 2D]) à l'instar des fonctions trigonométriques [une période].
Revoir aussi Escher (en teintes pastelles ici, et pavage "déformé aléatoirement")…

Bob (2017-04-10T13:59:48Z)

Ah oui, je n'avais pas réalisé que l'intersection des cellules de Voronoï en 8 dimensions avec le plan serait la même chose que les cellules de Voronoï en deux dimensions de l'intersection du plan avec le réseau.

C'est décidément dur à visualiser, 8 dimensions…

Ruxor (2017-04-10T13:48:30Z)

@Bob: Pour ce qui est du plan des deux premières coordonnées, ça fait juste un bête damier en losanges. (En fait, avec mon système de coloriage, c'est encore pire, ça fait juste une image totalement grise. Mais les cellules de Voronoï sont en losanges.)

Bob (2017-04-10T13:22:57Z)

Sinon pour le futur réseau candidat à la dissection, je vote pour D4, qui me semble offrir un bon compromis entre simplicité (on a une base naturelle orthonormée pour écrire le réseau) et symétrie (automorphismes extérieurs exceptionnels).

Bob (2017-04-10T13:12:25Z)

Très joli !

Pourrait-on voir ce que donne la section par un plan "le moins aléatoire possible" ? Par exemple le plan généré par (1,0,0,0,0,0,0,0) et (0,1,0,0,0,0,0,0) et passant par l'origine ?

Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: `953521`

• Comments will not appear until they have been reviewed by the moderator.
• HTML is not allowed in content or elsewhere (writing `<foo>` simply produces <foo> in the text).
• To cite a URL, write `<URL: http://somewhere.tld/ >`, and it will be automatically made into a link. (Do not try any other way or it might count as an attempt to spam.)
• To leave a contact address for all readers, use the Web site address field (it can be a `mailto:` URI, e.g. `mailto:my.email@somewhere.tld`, if you do not have a genuine Web site).