Figure 1 In step 1, the data is dividing into cells. In step 2, the average of each cell is calculated. In the third step new cell boundaries are calculated between the centroids. If a cell contains no points, the cell is removed.
Lloyd's method is attempting to solve a non-linear problem by an iterative scheme, so local minima can be problematic. To avoid prejudicing the solution the initial model is often a random set of vectors. To solve the problem, several methods have been developed Linde et al. (1980). These methods often rely on replacing an empty cell by splitting regions with high variance. Clapp (2002) followed a modified version of this approach for the velocity selection problem. Figure shows a velocity model, the selected reference velocities, and the percentage error between the two using the methodology described in Clapp (2002). The methodology proved effective in selecting appropriate reference velocities with two noticeable drawbacks. At each depth step a new non-linear estimate is performed. At some depths steps the solution gets stuck in local-minima. Note the striping in the right panel of Figure . In addition, the methodology will sometimes pick too few reference velocities to adequately describe a layer by getting stuck in a local minima. Both of these problems can be minimized by using as a starting solution the reference velocities at the previous depth step and adding a random component to the cell splitting. Figure shows the selected reference velocities and the percentage error in the selected reference velocities.