En mathématiques et en informatique, plus particulièrement en géométrie algorithmique, l'algorithme de Preparata-Hong est une méthode algorithmique pour calculer le plus petit polygone (dans le plan) ou polyèdre (dans l'espace) qui englobe un ensemble fini de points donnés. Autrement dit, il s'agit de calculer l'enveloppe convexe d'un ensemble fini de points dans l'espace euclidien de dimension 2 (le plan) ou de dimension 3 (l’espace). Cette méthode a été mise au point par Franco Preparata et Su Ji Hong[1]. Sa stratégie repose sur le paradigme connu en informatique sous le nom de « diviser pour régner ». Cet article présente uniquement le cas de la dimension 2.
- (en) Franco P. Preparata et Su Ji Hong, « Convex Hulls of Finite Sets of Points in Two and Three Dimensions », Communications of the ACM, vol. 20, no 2, , p. 87-93 (lire en ligne).