Minimizing Local Minima in Terrains with Higher-Order Delaunay Triangulations
Thierry de Kok, Marc J. van Kreveld, Maarten Löffler · 2005
We show that triangulating a set of points with elevations such that the number of local minima of the resulting terrain is minimized is NP-hard for degenerate point sets. The same result applies when there are no degeneracies for higher-order Delaunay triangulations. Two heuristics are presented to minimize the number of local minima for higher-order Delaunay triangulations, and they are compared experimentally.