Triangulations of point sets — obtuse and acute triangles

Question

Given a planar configuration of points in general position. It is known that the Delaunay triangulation is the 'fattest' triangulation possible. It is also easily seen that given 7 points with 6 of them close to the vertices of a regular hexagon and the 7th near its center, there is one triangulation where all 6 resulting triangles are acute and another giving all 6 obtuse triangles.

Questions:

1. Given n planar points, how does one algorithmically achieve a triangulation of n planar points such that (a) the number of acute triangles is maximized (b) the number of obtuse triangles is maximized? What are the best/worst point configurations for these triangulations?

Observation: if the input points lie (say) very close to a circular arc of small angle measure, all triangles in any triangulation are necessarily obtuse. There don't appear to be non-trivial point systems with all triangles in any triangulation being acute.

2. Does the Delaunay triangulation also minimize the (a) sum of the lengths of all edges and (b) sum of the diameters of the triangles ? If not, how does one achieve such triangulation(s)?

Note: In all the above, we do not add extra vertices.

Answer 1

The answer to 2(a) is No, the Delaunay triangulation does not minimize the sum of all edge lengths. That is known as the minimum weight triangulation, on which there is a considerable literature.

---

   

This is a quarter of the full example. The Delaunay triangulation is on the left. But the triangulation in (b) is much shorter.

(Figure from p.87 of Discrete and Computational Geometry.)