Polygone au volume minimum

Bonjour,

Voici mon problème :

J'ai un ensemble de 256 points dans un espace 3D, chaque point est donc représenté par 3 valeurs (x, y, z) tel que 0 <= x, y, z <= 511.

J'aimerais savoir s'il existe un algorithme permettant, pour un nombre T de points, de sélectionner parmi mes 256 points T points de façon a respecter les deux conditions suivantes :
- le polygone créé à partir des T points contient tous les autres 256-T points
- le polygone créé à partir des T points possède le volume minimum parmi les autres polygones possibles respectant la première condition

Je vous remercie d'avance de votre aide, ne serait-ce que si vous avez une piste :)

Bonne soirée !

Tu peux déjà commencer par une enveloppe convexe, ce qui assure la première condition.
Ensuite, pour la deuxième c'est très délicat de par sa définition. Parce que si l'on pousse à l'extrême, la solution finale est en fait un graphe reliant tous les T-Points.
Mais à partir de l'enveloppe convexe, tu peux faire une méthode itérative :
- pour chaque point ne formant pas l'enveloppe
- trouver les trois points de l'enveloppe les plus proches
- déformer l'enveloppe en incluant le nouveau point si cela ne fait pas sortir un autre T-Point.

Salut!
Juste une petite remarque concernant le vocabulaire: dans un espace 3d, il ne s'agit pas d'un polygone mais d'un polyèdre.
Jean-Marc Blanc

Bonjour,

Tout d'abord merci à vous deux pour vos réponses, et particulièrement à ToTo13 dont la réponse m'a été très utile. Merci à FR119492 pour cette précision :)

Pour apporter un petit complément d'information, voici la page wikipédia relatant les algorithmes pour former l'enveloppe convexe :
http://en.wikipedia.org/wiki/Convex_hull_algorithms

Tous ne se généralise pas à des points en 3D. La complexité temporelle de ces algorithmes est au minimum en O(n log n), n étant le nombre de points en entrée. Cependant, certains algorithmes ont une complexité temporelle qui se caractérise en fonction de n et de h, h étant le nombre de points nécessaire pour former l'enveloppe. Ces algorithmes sont appelés output-sensitive algorithms. C'est notamment le cas de l'algorithme de Chan (http://en.wikipedia.org/wiki/Chan%27s_algorithm) dont la complexité est en O(n log h) et qui se généralise à des points en 3D.

Parfait :D Merci encore !