Discussion :

[Aleph69]

Bonjour,

je dispose d'un ensemble de vecteurs définissant chacun une cellule de voronoï (et je connais les frontières de mon domaine). La dimension de l'espace peut-être plus ou moins grande mais est en général supérieure à 10.
J'aimerais estimer les volumes de mes cellules de Voronoï.
Je sais qu'il existe des méthodes de calcul en géométrie algorithmique mais la complexité n'est pas acceptable en grande dimension.
J'avais pensé à faire du monte-carlo mais je me demande s'il n'y a pas mieux, par exemple en passant par de l'intégration numérique.

Si quelqu'un a une idée ou connaît une méthode, je suis preneur.

[Nemerle]

... faudrait préciser un poil là.

[Aleph69]

J'ai un ensemble fini de vecteurs, notons-le E, sous-ensemble de R^p.
La dimension p peut-être grande (ex:1000).
Si w est un vecteur dans E, il définit la cellule de Voronoi C(w) :

C(w) = { x dans R^p; ||x-w||<= ||x-w*||, pour tout w^* dans E}.

On admet qu'il existe au moins un vecteur dans E qui définit une cellule de Voronoï finie.
Comment estimer le volume de cette cellule?

[pseudocode]

J'ai un ensemble fini de vecteurs, notons-le E, sous-ensemble de R^p.
La dimension p peut-être grande (ex:1000).
Si w est un vecteur dans E, il définit la cellule de Voronoi C(w) :

On admet qu'il existe au moins un vecteur dans E qui définit une cellule de Voronoï finie.
Comment estimer le volume de cette cellule?

Ca dépend de la précision de l'estimation

On peut simplement calculer le volume de la boite-englobante de la cellule

On peut découper l'espace en volumes élémentaires et faire une sommation des éléments intérieurs a la cellule

On peut calculer le volume de la cellule par intégration différentielle (théorème de Stokes)

etc.

[Aleph69]

Mon problème est que mes cellules de Voronoï sont définies de manière implicite : je n'en connais pas la frontière explicitement.
Je ne vois pas comment définir une boîte englobante ou découper ma cellule ou calculer le volume par la formule de Stokes.

[pseudocode]

Mon problème est que mes cellules de Voronoï sont définies de manière implicite : je n'en connais pas la frontière explicitement.
Je ne vois pas comment définir une boîte englobante ou découper ma cellule ou calculer le volume par la formule de Stokes.

Ah. Je comprend mieux ton idée de monté-carlo, qui consiste en fait à obtenir une approximation de la représentation explicite des cellules.

Et à moins d'avoir une formulation explicite des cellules, je ne vois pas comment faire.

[Aleph69]

Et à moins d'avoir une formulation explicite des cellules, je ne vois pas comment faire.

A ma connaissance, la construction explicite du diagramme de Voronoï est beaucoup trop chère car la dimension de l'espace apparaît en exposant dans la complexité.

Merci quand même d'avoir essayé.

[Nemerle]

heu... la méthode directe ne fonctionne pas?

Ta cellule Cw est un polyhèdre définis par les hyperplans perpendiculaires au droites (w,w') et passant par leurs milieux.

Une réduction linéaire sur les equations de ces hyperplans te fournit alors le simplexe de sommets s1...sN, et il me semble qu"une notion de volume est donnée par det(s1....sN)/N!

M'enfin, il ne faut pas non plus que ton ensemble E contienne des milliards de points... [EDIT] je viens d'avoir ma réponse, si en plus p est dans la complexité ... pas de triangulation donc [/EDIT]

[Aleph69]

heu... la méthode directe ne fonctionne pas?

Si elle fonctionne mais elle est impraticable car la complexité dépend de la dimension de l'espace qui apparaît en exposant (en tous cas pour les méthodes que je connais).

[Nemerle]

si tu n'as pas besoin d'évaluation réellement "précise", tu peux chercher l'intersection de la cellule avec les 1000 axes e_1...e_1000 de ton repère:

Pour chaque 1<=i<=1000, tu cherches C(w) inter R.e_i.

Ca revient à déterminer le Xmax_i et le Xmin_i tel que d(w,w+Xi.e_i)<=d(w',w+Xi.e_i) pour tout w' avec Xi=Xmax_i ou Xmin_i.

Tu calcules alors l'aire du polyhèdre de sommets ces 2000 points...