Volume minimal contenant p points

[Anonyme]

Bonjour,

Je souhaiterais avoir une mesure du volume occupé par un ensemble de p
points en dimension n. Le calcul de l'enveloppe convexe étant trop long,
j'envisageais de calculer le volume du plus petit
(hyper?)-parallélépipède contenant les p points.

Mes questions sont donc:
- y a-t-il une borne du rapport entre les 2 volumes précités?
- pour calculer le plus petit parallélépipède (ou une approximation),
j'envisageais de prendre des arêtes selon les k premiers vecteurs
propres de la Matrice de Gram associée aux p points et de prendre n-k
vecteurs orthogonaux au pif. Quelqu'un a une meilleure idée?

Merci beaucoup.

--
Genji
L'homme n'était pas grand, la femme était maigre. Il était blême, elle
était blafarde. Tous deux vêtus de noir, ils semblaient porter
ironiquement le deuil de leur santé. -- Sacha Guitry

[Anonyme]

Nicolas Le Roux , dans le message (fr.education.entraide.maths:49746), a
écrit :
> Mes questions sont donc:
> - y a-t-il une borne du rapport entre les 2 volumes précités?

Un truc en 1/n!... enfin en tout cas, ça marche pour n=2 et n=3, et
ça a l'air de se généraliser par récurrence sans aucun problème, si
on sait calculer le volume d'un cône en dimension d.

> - pour calculer le plus petit parallélépipède (ou une approximation),
> j'envisageais de prendre des arêtes selon les k premiers vecteurs
> propres de la Matrice de Gram associée aux p points et de prendre n-k
> vecteurs orthogonaux au pif. Quelqu'un a une meilleure idée?

Euh... sais pas.

--
Xavier, qui n'ai jamais bien compris les matrices de Gram de toute
façon.

[Anonyme]

Le Fri, 24 Oct 2003 23:00:01 +0000 (UTC),
Xavier Caruso grava à la saucisse et au marteau:

> Nicolas Le Roux , dans le message (fr.education.entraide.maths:49746), a
> écrit :[color=green]
> > Mes questions sont donc:
> > - y a-t-il une borne du rapport entre les 2 volumes précités?
>
> Un truc en 1/n!... enfin en tout cas, ça marche pour n=2 et n=3, et
> ça a l'air de se généraliser par récurrence sans aucun problème, si
> on sait calculer le volume d'un cône en dimension d.[/color]

Merci Papa (mais moi je voulais pas en dimension d, je voulais en
dimension n).

--
Genji, qui comprenons pas très bien les matrices de Gram non plus
L'homme n'était pas grand, la femme était maigre. Il était blême, elle
était blafarde. Tous deux vêtus de noir, ils semblaient porter
ironiquement le deuil de leur santé. -- Sacha Guitry

[Anonyme]

Le Fri, 24 Oct 2003 23:00:01 +0000 (UTC),
Xavier Caruso grava à la saucisse et au marteau:

> Nicolas Le Roux , dans le message (fr.education.entraide.maths:49746), a
> écrit :[color=green]
> > Mes questions sont donc:
> > - y a-t-il une borne du rapport entre les 2 volumes précités?
>
> Un truc en 1/n!... enfin en tout cas, ça marche pour n=2 et n=3, et
> ça a l'air de se généraliser par récurrence sans aucun problème, si
> on sait calculer le volume d'un cône en dimension d.[/color]

Merci Papa (mais moi je voulais pas en dimension d, je voulais en
dimension n). Donc ça dépend pas du nombre de points si j'ai bien
compris. Et le nombre minimal de points pour parvenir à ce rapport,
c'est quoi? 2^(n-1)+1?

--
Genji, qui comprenons pas très bien les matrices de Gram non plus et qui
essaye de deviner le nombre de points minimal à partir de la remarque de
Xavier sur le cône.

[Anonyme]

Xavier Caruso, dans le message (fr.education.entraide.maths:49747), a
écrit :[color=green]
>> - y a-t-il une borne du rapport entre les 2 volumes précités?
>
> Un truc en 1/n!... enfin en tout cas, ça marche pour n=2 et n=3, et
> ça a l'air de se généraliser par récurrence sans aucun problème, si
> on sait calculer le volume d'un cône en dimension d.[/color]

En fait, j'avais mal compris la question, et puis de toute façon, il
me semble que la réponse que j'ai donnée n'est valable pour aucune
des questions que j'aurais pu comprendre.

Bref, oublie ce que j'ai dit, je devais être fatigué hier soir.

[Anonyme]

Le Sat, 25 Oct 2003 07:13:12 +0000 (UTC),
Xavier Caruso grava à la saucisse et au marteau:

> En fait, j'avais mal compris la question, et puis de toute façon, il
> me semble que la réponse que j'ai donnée n'est valable pour aucune
> des questions que j'aurais pu comprendre.

T'avais compris quoi, dis? Je sais qu'en tout cas, avec 100 points en
dimension 10, j'ai eu un rapport de 1 à 10000 entre le volume de
l'enveloppe convexe et celui du parallélépipède minimal.

--
Genji
L'homme n'était pas grand, la femme était maigre. Il était blême, elle
était blafarde. Tous deux vêtus de noir, ils semblaient porter
ironiquement le deuil de leur santé. -- Sacha Guitry

[Anonyme]

Nicolas Le Roux , dans le message (fr.education.entraide.maths:49794), a
écrit :
> T'avais compris quoi, dis?

Ben, je sais pas trop en fait .

> Je sais qu'en tout cas, avec 100 points en dimension 10, j'ai eu un
> rapport de 1 à 10000 entre le volume de l'enveloppe convexe et celui du
> parallélépipède minimal.

Quand j'avais essayé de réfléchir à ta question, je m'étais dit qu'il
était peut-être mieux de considérer un vecteur propre associé à la
plus grande valeur propre, tout projeter sur l'orthogonal de la droite
dirigée par ce vecteur et recommencer récursivement.

Mais je sais plus non plus maintenant pourquoi je m'étais dit ça,
donc c'est peut-être totalement foireux. .

--
Xavier, qui, en plus, ai mal à la tête et ai du repassage à faire.

[Anonyme]

Le Sun, 26 Oct 2003 15:35:04 +0000 (UTC),
Xavier Caruso grava à la saucisse et au marteau:

> Quand j'avais essayé de réfléchir à ta question, je m'étais dit qu'il
> était peut-être mieux de considérer un vecteur propre associé à la
> plus grande valeur propre, tout projeter sur l'orthogonal de la droite
> dirigée par ce vecteur et recommencer récursivement.

Bah, en l'occurrence, pour choisir le parallélépipède minimal, je prends
des arêtes parallèles aux vecteurs propres associées aux n valeurs
propres non nulles. Mais ptet que je me gourre totalement aussi

--
Genji
L'homme n'était pas grand, la femme était maigre. Il était blême, elle
était blafarde. Tous deux vêtus de noir, ils semblaient porter
ironiquement le deuil de leur santé. -- Sacha Guitry

[Anonyme]

Nicolas Le Roux , dans le message (fr.education.entraide.maths:49807), a
écrit :
> Bah, en l'occurrence, pour choisir le parallélépipède minimal, je prends
> des arêtes parallèles aux vecteurs propres associées aux n valeurs
> propres non nulles. Mais ptet que je me gourre totalement aussi

Moi, finalement, je me dis que prendre un pavé n'est peut-être pas une
idée si lumineuse. Par exemple, si le polyèdre (enfin du volume -- je sais
pas comment il faut dire en dimension n) est déterminé par seulement
n+1 points, il n'est pas très dur de voir que le volume de ce polyèdre
sera toujours inférieur à 1/n! fois le volume du pavé. Et 1/n! quand n=10
c'est grand.

Tu vas me dire que si tu as beaucoup de points, tu as peu de chance d'être
dans cette situation, mais bon quand même... je pense que ça peut suffire
à expliquer tes écrats importants.

Mais, si c'est dur que ça de déterminer l'enveloppe convexe ; il me semble
qu'il y avait des algorithmes efficaces, du moins en dimension 2 et 3.
Maintenant peut-être, ca se généralise mal, je sais pas.

[Anonyme]

Le Sun, 26 Oct 2003 19:40:33 +0000 (UTC),
Xavier Caruso grava à la saucisse et au marteau:

> Mais, si c'est dur que ça de déterminer l'enveloppe convexe ; il me semble
> qu'il y avait des algorithmes efficaces, du moins en dimension 2 et 3.
> Maintenant peut-être, ca se généralise mal, je sais pas.

En tout cas, avec 100 points en dimension 10, le temps de calcul sous
Matlab est sans commune mesure avec celui du parallélépipède minimal.

--
Genji
L'homme n'était pas grand, la femme était maigre. Il était blême, elle
était blafarde. Tous deux vêtus de noir, ils semblaient porter
ironiquement le deuil de leur santé. -- Sacha Guitry