2
$\begingroup$

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.

  1. 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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.


   MinWeightTri

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.)

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for pointing out minimum weight triangulation - had overlooked it. Nice example! And it settles question 2b too in the negative! The remaining bit in question 2 is how to find the least diameter sum triangulation - whether it has any connection to minimum weight triangulation. $\endgroup$ May 22, 2021 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.