## 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 linear 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 higher order Delaunay triangulations.

keywords: Computational Geometry, Delaunay Triangulations, Fixed-Parameter Tractability, Terrains

### Journal Article (peer-reviewed)

Maarten Löffler, Marc van Kreveld, Rodrigo I. Silveira

Optimization for First Order Delaunay Triangulations

Computational Geometry: Theory and Applications

43, 377-394, 2010

### Conference Proceedings (peer-reviewed)

Maarten Löffler, Marc van Kreveld, Rodrigo I. Silveira

Optimization for First Order Delaunay Triangulations

Proc. 10th Workshop on Algorithms and Data Structures

LNCS 4619, 175–187, 2007

*Invited to Special Issue of CGTA*

### Workshop or Poster (weakly reviewed)

Maarten Löffler, Marc van Kreveld, Rodrigo I. Silveira

Optimization for First Order Delaunay Triangulations

Proc. 13th Conf. Advanced School for Computing and Imaging

393–400, 2007

### Technical Report (not reviewed)

Maarten Löffler, Marc van Kreveld, Rodrigo I. Silveira

Optimization for First Order Delaunay Triangulations

UU-CS-2007-011, 2007

back to list