Nombre de faces d'un polyèdre

Tu peux considérer tous les $n$-uplets $(M_1,\dots,M_n)$ de points appartenant à $S$ tels que $(M_2-M_1, M_3-M_1, \dots, M_n-M_1)$ est de rang $n-1$. Si pour tout autre point $M$ de $S$, le déterminant de $(M_2-M_1, M_3-M_1, \dots, M_n-M_1,M-M_1)$ ne change pas de signe en fonction de $M$, alors $M_1, M_2, \dots, M_n$ appartiennent à une même face de l'enveloppe convexe de $S$.

Ensuite rassembler tous les points qui appartiennent à une même face.

Il y a certainement mieux comme algorithme.

Hello,
Il faut déjà prendre conscience que déterminer les sommets d'un polytope construit comme enveloppe convexe d'un nombre fini de points à coefficients rationnels ou entiers, c'est pas mal de travail. Un problème plus simple est de certifier, pour un vecteur $v \in \R^n$ et une famille finie $(v_i)_{i \in I}$ de vecteurs de $\R^n$ si l'on a ou pas l'appartenance :
$$
v \in \sum_i \R^+ v_i
$$
(alternative de Farkas-Fourier). Ici $\R$ désigne n'importe quel sous-corps de $\mathbb R$.

Ci-dessous, histoire de faire joujou, je tire au hasard 20 points (entiers) d'un réseau de dimension 3.

> n := 3 ;                                                     
> L := ToricLattice(n) ;
> L ;
3-dimensional toric lattice L = Z^3
> S := [L| [Random(-5,5) : i in [1..n]] : howmany in [1..20]] ;
> S ;
[
    (-3, -1, 4),
    (4, -4, -1),
    (1, -3, 5),
    (-4, -1, 0),
    (4, 5, 4),
    (-4, -5, 4),
    (-5, 3, 1),
    (0, -1, 2),
    (4, -3, -4),
    (4, -1, -2),
    (5, -1, 3),
    (-3, 2, 1),
    (3, 1, 3),
    (2, 1, -2),
    (-1, 5, -4),
    (-1, 3, -1),
    (-1, 3, 4),
    (-1, 2, -1),
    (-3, 3, -3),
    (-3, 4, 0)
]

Je n'ai absolument pas regardé ce que je fabriquais (il y a peut-être plusieurs fois le même point, mais peu importe). Il y a peu de chances que ces 20 points soient les 20 sommets du polytope enveloppe convexe.

> P := Polytope(S) ;                                           
> #Vertices(P) ;                                               
13
> P : Maximal ;
3-dimensional polytope P in 3-dimensional toric lattice Z^3 with 13 vertices:
    (-3, -1,  4),
    ( 4, -4, -1),
    ( 1, -3,  5),
    (-4, -1,  0),
    ( 4,  5,  4),
    (-4, -5,  4),
    (-5,  3,  1),
    ( 4, -3, -4),
    ( 5, -1,  3),
    (-1,  5, -4),
    (-1,  3,  4),
    (-3,  3, -3),
    (-3,  4,  0)
with 22 facets.

Ci-dessus, dès la demande du nombre de sommets (égal à 13) un certain nombre de calculs ont été élaborés de manière interne (par exemple écriture du polytope comme intersection d'un nombre fini de demi-espaces rationnels, structure du graphe d'incidence ...etc...)

La relation d'Euler :

> #Faces(P,0), #Faces(P,1), #Faces(P,2), #Faces(P,3) ;
13 33 22 1
> #Faces(P,0) - #Faces(P,1) +  #Faces(P,2) - #Faces(P,3) ;
1

@DinoH
C'est magma. Je pense que Sage (que je ne connais pas) doit fournir des fonctionnalités analogues. Au hasard : http://doc.sagemath.org/html/en/thematic_tutorials/polytutorial.html http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/lattice_polytope.html http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/library.html https://www.math.aau.at/user/cheuberg/sage/doc/6.10.beta3/en/reference/geometry/sage/geometry/polytope.html

Quant à l'installation de Sage sur Windows, il faut demander aux experts (tu peux peut-être ouvrir un fil dans la rubrique Informatique ?)