Mètode de Graham

De Viquipèdia
Jump to navigation Jump to search

El mètode de Graham (Graham scan) és un mètode de càlcul computacional de l'envolupant convexa d'un grup finit de punts en el pla de complexitat. El nom fa honor a Ronald Graham, qui va publicar l'algorisme el 1972.[1] L'algorisme calcula tots els vèrtexs de l'envolupant convexa ordenats al llarg de la frontera. Pot ser modificat fàcilment per trobar els punts que, sense ser vèrtexs, pertanyen a aquesta envolupant.

Referències[modifica]

  1. Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133