Optimization for first order Delaunay triangulations

This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of only to single triangles. We give efficient algorithms to optimize certain measures, including measures related to the area ratio of adjacent triangles, angle between outward normals of adjacent triangles (for polyhedral terrains), and number of convex vertices. Some other measures are shown to be NP-hard. These include maximum vertex degree, number of convex edges, and number of mixed vertices. For the latter two measures we provide, for any constant ε>0, factor (1−ε) approximation algorithms that run in 2O(1/ε)⋅n and 2O(1/ε2)⋅n time (when the Delaunay triangulation is given). For minimizing the maximum vertex degree, the NP-hardness proof provides an inapproximability result. Our results are presented for the class of first order Delaunay triangulations, but also apply to triangulations where for every triangle at least two edges are fixed. The approximation result on maximizing the number of convex edges is also extended to k-th order Delaunay triangulations.