I know that that the Delaunay triangulation maximizes the minimum angle of triangulation. And it does not minimize the maximum angle. If we consider the set of points in general position(no four points are co-circular). Can someone please give a simple example where the Delaunay triangulation does not minimize the maximum angle.


This animation from the wikipedia article on delaunay triangulations shows you an example of where the delaunay triangulation will switch from having a horizontal interior edge to a vertical interior edge:


The moment this configuration switches to a horizontal interior edge, it is showing that the delaunay triangulation prefers a triangulation with a smallest maximum angle of 88-ish degrees to one that has a smallest maximum of 66-ish degrees.

  • $\begingroup$ Thank You. I think you mean 120-ish instead of 66-ish? $\endgroup$ – Inuyasha yagami Mar 11 '20 at 10:36
  • $\begingroup$ I meant 66ish because I thought we were considering the minimum (smallest) of all the maximum angles in the triangulation, where a 'maximum angle' is the largest angle in each triangle. So I was looking at the smallest of those maximum angles as our objective value. But if you just mean to minimize the overall largest angle in the whole triangulation, then, yes, 120-ish. Luckily, the transition in the example gives an example for both measures. $\endgroup$ – JimN Mar 15 '20 at 3:46

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.