If all you know is "convex polyhedron," it is impossible to tell. Reason? "polyhedron" implies that the surface is made of faces bounded by polygons, but polygons can have any number of vertices. Lets say you have a triangle mesh, a tetrahedron. That has 4 faces, all triangles, and 4 vertices. And 6 edges. Applying Euler's characteristic:

F-E+V = 2 B

Here, we have one body, so 4-6+4=2, which works.

Now, subdivide every edge once so that you now have vertices in the center of each edge. You still have a polyhedron. It still satisfies the Euler characteristic. 4 faces. 12 edges. 10 vertices. We added just as many edges as we added vertices, so no net change to the Euler formula. The faces are still polygons, just no longer 3 node triangles (and might not be considered triangles at all if you define a triangle to have 3 nodes exactly...though the faces are triangular shaped and planar in this case).

Anyway...the point of that is...there is, for a general polyhedron, NO upper bound on the number of edges as a function of face count and therefore NO upper limit on the number of vertices.

Next reply. Now...if you know your polyhedron to be defined by triangles only, and you define a triangle to be exactly 3 vertices and 3 edges, the problem is much easier and there are bounds. Lets look at a single face. 1 face. 3 edges. 3 vertices. The number of vertices = 3 times the number of faces. The assumption here is that the number of unique, unshared vertices is 3 per face. Triangle soup. That is a loose upper bound. Euler's formula can only be satisfied here when there are 2 faces, and that is a failure case for Euler's formula because a body made of 2 disconnected triangles isn't watertight.

So we have a loose upper bound on a triangle-based polyhedron: # vertices = 3 times the number of faces. Can we get a tighter upper bound? Look at a tetrahedron, for example. The ratio of edges to faces is 6-to-4. If we split an edge, we add an edge and we add a face. New ratio 7-to-5. Split another edge, add an edge and a face (one face turns into two leaving one new one). New ratio 8-to-6. Trend for this case is max#edges = n + 2, with n = number of faces. Can we exceed that, e.g., is that really an upper limit or is it too low or high? Lets look at it another approach. Split faces at the centroid instead of splitting edges. Split a face and you get 3 new edges and 2 new faces (one face turns into 3 leaving 2 new ones). So starting from a tetrahedron with a ratio of 6-to-4, if you split one face the ratio goes to 9-to-6. Split another face and the ratio goes to 12-to-8. So, different result! The number of edges is greater! So, our max#edges = n + 2 rule is wrong. We can exceed that by splitting faces instead of edges. The new rule seen here would be max#edges = 3n/2. Does that work in every case? For the baseline tetrahedron? Yes. For one edge split? Yep. (Remember, its an upper limit...actual value in this case is 7.5, not an integer, but even if we take the floor of the integer our estimate of the # of edges does not exceed the actual 3 of edges.) Two edge splits? Yep. (Overestimates by 1.) For face splits only, its always exact. So, I think this rule is good.

So, for a triangle-based polyhedron, the max#edges = floor(3n/2), with n = number of faces. Compute the max#vertices from the Euler formula, using the actual n and the computed max#edges.

Er...now...topology is stranger than you think. I think that rule is probably good as long as you stick to triangles (covered in prior post), and require that your convex polyhedron be a strict watertight manifold, e.g., obviously if your mesh definition has dangling edges (not bounding at least 2 faces), dangling vertices (not connected to at least 2 edges), or overused things (edges connected to more than 2 faces), you're going to have problems.

Vorpy, for strictly triangle based, manifold polyhedrons, did I miss anything in my analysis?

Quote:Original post by Vorpy
Each vertex must have exactly 3 edges. It is not possible for a vertex to have less than 3, and if there are more than 3 then we can split the vertex into two vertices with an edge between them, creating a shape with more vertices.

But you have introduced a new constraint here, and the solution to guarantee the constraint is satisfied involves creation of degenerate (zero length) edges, and potentially an unlimited number of them at a given location (think of a triangle fan with ten thousand triangles connecting to a vertex...quite legal for a general convex polyhedron). Also, whenever you create a degenerate edge, you also have to create a degenerate, zero area triangle (which you meant but just didn't say). Otherwise, you would create a crack in the model, which would make it nonmanifold.