d'un ensemble de points de R^n.

De manière faisable évidemment "algorithmiquement", on se donne k points de R^n et j'aimerais savoir s'ils peuvent former un polytope convexe.

Encore en se limitant à des cas de 2-D ou 3-D on pourrait trouver des trucs bricolés, mais généraliser à N dimensions je coince pas mal.

d'avance.

Précise ce que tu veux, parce qu'il suffit de prendre l'enveloppe convexe de tes k points pour répondre à la question.

Si tu as fixé un ordre de parcours (genre dans le plan, relier le numéro 1 au numéro 2 au ... au numéro k au numéro 1), c'pas compliqué, une condition nécessaire est que tout segment [i,j] où i et j sont les points numéros i et j soit encore dans le polytope défini.

Je ne vois pas en quoi c'est si évident. Comment tu vérifies cette condition nécessaire ? Quelle définition donnes-tu de ton polytope ?

Cela dépend peut-être du langage utilisé, mais en Matlab je ne trouve pas ça si simple. Mais j'espère avoir tort !

Ce que veut dire Hachino c'est qu'en prenant l'enveloppe convexe de tes k points (ie le plus petit convexe qui contient tes k points, ie l'ensemble des barycentres à coeff >=0 de tes k points), tu obtiens un polytope convexe à partir des k points.
Mais dans ce cas il se peut que certains des points soient à l'intérieur, et donc ne servent pas à grand chose. Faut préciser si tu veux éviter cette situation.