Polyèdre convexe

[Vana7614]

Bonjour !!!

Je dispose d'un ensemble de points en n dimensions et j'aimerai construire le polyèdre convexe de ces points dans cette dimension...

Je ne vois pas du tout comment m'y prendre, je n'ai pas trouvé de théorème ou d'algorithme relatif à ce problème en n dimension (n>3). :mur:

Je pensais qu'il serait possible de travailler dans tous les sous espaces en 2 dimensions et ici d'y trouver chaque enveloppe convexe... Mais intuitivement, je pense que :
P est polyèdre convexe des points en n dimensions
n'est pas équivalent à
P = réunion des Pi (enveloppes convexes en 2 dimensions) est polyèdre convexe des points en n dimensions
.... Oui ? Non ? Comment le prouver, l'erroner ?

Merci pour vos conseils, suggestions, etc !

Bonne journée !

Vana

[Doraki]

Comment tu veux représenter un polyèdre en n dimensions ?

[Vana7614]

Je ne souhaite pas le représenter, je souhaite connaître ses points sommets à partir d'un ensemble de points... Si c'est faisable...

[Doraki]

Pour pouvoir calculer ça il faut savoir calculer des déterminants de matrices n*n, et particulièrement leur signe.

det(P1,P2,...,Pn) = le déterminant de la matrice où les colonnes sont constituées des coordonnées de chaque point Pi.

Un point Q est dans l'enveloppe convexe de (n+1) points P0,P2,...Pn si et seulement si les déterminants det(Q,P0...,Pn-2), det(Q,P1,...,Pn-1), det(Q,P2,...,Pn), det(Q,P3,...,Pn,P0) ... det(Q,Pn,P0...Pn-3) sont de même signe.

Après, y'a sans doute moyen de faire les calculs de manière plus ou moins astucieuse, mais de toutes façons ce sera compliqué.

[Doraki]

Pour calculer ça, tu as besoin de calculer des déterminants de matrices (n+1) * (n+1).

Si P0,...,Pn sont n+1 points, soit d(P0...Pn) le signe du déterminant de la matrice où les colonnes sont les coordonnées des points Pi, et avec une (n+1)ième coordonnée en plus qui vaut toujours 1.
(la dernière ligne de la matrice ne contient que des 1).

Alors un point Q est dans l'enveloppe convexe de P0 P1 .... Pn si et seulement si
d(P0...Pn) = d(Q,P1...Pn) = d(P0,Q,P2...Pn) = ... = d(P0,P1...Pn-1,Q).

Après y'a sans doute moyen de mener les calculs de façon plus ou moins astucieuse mais de toutes façons ce sera compliqué.