Jump to content
  • Advertisement
Sign in to follow this  
samgzman

Greatest number of vertices in an polyhedron with n faces

This topic is 3954 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to find a function that will give me a least upper bound (maximum) number of vertices in a convex polyhedron with n faces. I'm well aware of the Euler Characteristic, but in my case the number of Edges is unknown. If i could find a least upper bound on the number edges as a function of face count, I would essentially have the answer I am looking for. Anyone want to take a crack at it?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
If we also state that each (edit: pair of) faces has at most one edge between them, then there is a solution. A loose upper bound on the number of edges would be n*(n-1)/2, giving a characteristic of n - n*(n-1)/2 + V = 2, V = 2 - n + n*(n-1)/2. The least upper bound would be less than this, of course...

[Edited by - Vorpy on February 9, 2008 1:37:36 AM]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
For my problem, the polyhedron's edges are defined by the intersections of a finite set of aribitrarily oriented pairs of parallel planes. The polyhedron is defined by the intersection of all spaces between these pairs. The faces of the polyhedron are therefore coincident with these planes. I assume that any valid configuration establishes a closed manifold.

Share this post


Link to post
Share on other sites
I'm now thinking the answer is just 2*(n-2) vertices for a convex polyhedron with n faces.

Assume we have an n-hedron with the maximum number of vertices possible for the value n. 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. So each vertex has 3 edges. Each edge is shared between 2 vertices, so there are 3V/2 edges.

F - 3V/2 + V = 2
F - V/2 = 2
V = 2*(F-2)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I believe that whenever more than 3 edges meet at a single vertex, it is always possible to adjust the bounding planes of the convex polyhedron to split the vertex into two vertices connected by an edge, each of which will have at least 2 of the edges that were previously going to the original vertex. No degenerate edges or triangles are needed. The number of vertices and edges increases by 1, and this can be repeated until every vertex is connected to 3 edges.

I was looking into this a little, and I think this can be proven more mathematically. Apparently, convex polyhedra correspond to 3-connected planar graphs, planar graphs where every node has at least three independent paths to every other node. Given a 3-connected planar graph with a node of degree greater than 3, we can split the node into two nodes with an edge between them and give each of the new nodes half of the old node's edges.

This new graph must also be 3-connected. All of the old nodes still have the same number of independent paths to both of the new nodes. The two new nodes are at least 3-connected: They have an edge to each other, and each has at least two edges to different nodes that are 3-connected to the other new node (so there must be at least two independent paths between the new nodes that don't use the new edge).

Therefore it is always possible for a convex polyhedron to have exactly 3 edges for every vertex, regardless of the number of faces, and it shows that if a vertex has more than 3 edges, it is always possible to construct a new polyhedron with more vertices and the same number of faces. Therefore the polyhedron with 3 edges per vertex has the maximum number of vertices for the given number of faces.

Share this post


Link to post
Share on other sites
Let G be the average number of edges that meet at a vertex (over all vertices). Clearly, G>=3. Now we know that

G*V = E/2
E = G*V/2
F - (G*V)/2 + V = 2
F = 2 - V + G*V/2 >= 2 - V + 3*V/2 = 2 + V/2
F >= 2 + V/2
V <= (F-2)*2

Then you have to prove that there are polyhedra with that many vertices, but that's easy to do by induction.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!