Quick one for the mathemagicians... I've tried to google a straight answer for this but kept coming up with over verbose twaddle, and I'm sure someone will know the answers off the top of their head.

I'm constructing a 2d Delaunay triangulation of a set of 2d vertices, and I want to know ahead of time the maximum possible number of triangles and the maximum possible number of edges, given the number of verts.

• I've read a suggestion that the maximum tris may be n+1, where n is the number of verts. Can anyone confirm this?
• No idea on the edges, I'm sure it will be something simple. Obviously it can't be more than 3x the number of triangles, but I'm assuming it will always be lower than this because of triangles sharing edges.

Many thanks!

[EDIT: Answered too fast. Let me think about it a bit more. Sorry!]

Thanks alvaro!

maximum number of triangles = 2 * number of vertices - 5

maximum number of edges = 3 * number of vertices - 6

I was going to say, just tested your first formula, and didn't work, here's 5 verts with 4 tris. But you beat me to it!

In case anyone is interested in a proof, here it is.

If n is the number of vertices and b is the number of vertices on the boundary of the convex hull of all the points, we can add up the inner angles of all the triangles in two different ways. The angles formed around an interior point add up to 2*pi. The angles formed around a point on the boundary of the convex hull add up to pi minus a little bit. Those little bits add up to 2*pi, as you go around the convex hull once. The other way of counting it is pi * number of triangles. So we get

pi*number of triangles = 2*pi*(n - b) + pi*b - 2*pi

Dividing by pi,

number of triangles = 2*n - b - 2

The minimum value for b is 3, so the maximum number of triangles is 2*n - 5

For the number of edges, you can use 3 * number of triangles, but most edges would have been counted twice. The edges that are not counted twice are the ones on the boundary of the convex hull, so there are b of them. You can then count the number of edges, like this:

number of edges = (3 * number of triangles + b) / 2 = (6*n - 3*b - 6 + b) / 2 = 3*n - b - 3

As before, the minimum value for b is 3, so the maximum number of edges is 3*n - 6