Abstract: Delaunay triangulation is an effective method for establishing digital terrain model，however，it introduces some problems such as artificial dams and local minima，which doesn’t reflect the realistic terrain.In this paper，the higher order triangulation that is an extension of the Delaunay triangulation is introduced，and the generation algorithm of the higher order triangulation is given.This method can effectively reduce the numbers of artificial dams and local minima.The algorithm has been implemented in five different terrains，showing that the method can effectively reduce the numbers of the local minima.So，it is more realistic for generating terrains model with higher order Delaunay triangulations.