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
http://dx.doi.org/10.1016/j.comgeo.2009.01.010

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
http://dx.doi.org/10.1007/978-3-540-73951-7_16
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
http://www.cs.uu.nl/research/techreps/UU-CS-2007-011.html

back to list