The Voronoi diagram is a decomposed region X made into cells, the decomposition being induced by a set of generators (Pk)k-K, and a distance function, and involves finding for each generator Pk a cell, which is a set of all the points in X satisfying the condition that the distance to the current generator P=Pk is not greater than the distance thereof to the union A of the other generators. For each generator, and for each point p in this generator, the method selects a set of directions, then for each direction recursively tests a ray in that direction, until a certain interval on the ray is shorter than or equal to a given error parameter. A point corresponding to the interval on the ray is then selected as an end point, and cells are defined from the end points, thus forming the Voronoi diagram.