Started by Feb 08 2008 05:29 PM

,
15 replies to this topic

Posted 08 February 2008 - 05:29 PM

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?

Posted 08 February 2008 - 06:02 PM

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.

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,

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 08 February 2008 - 06:37 PM

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]

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

Posted 08 February 2008 - 06:48 PM

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.

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

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.

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 08 February 2008 - 06:50 PM

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

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 08 February 2008 - 08:38 PM

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.

Posted 08 February 2008 - 09:10 PM

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)

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)

Posted 10 February 2008 - 05:44 AM

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.

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 10 February 2008 - 09:17 AM

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.

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.

Posted 10 February 2008 - 10:46 AM

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.

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.

Posted 11 February 2008 - 06:13 AM

Quote:

Original post by Vorpy

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.

Yes, but you are changing the boundary geometry. To accomplish the non-degenerate edges/triangles, the split vertices must not be coincident and even if the new vertex lies along one of the existing edges, you can only guarantee that the two faces that share the edge onto which the new vertex is inserted will be on the same plane they were on before the split. The convex hull becomes different when you do this. If samgzman's input plane pairs are prescribed and must be fixed, then there may not be the luxury of changing the hull. But, perhaps this isn't a requirement. I don't believe I have enough information to be sure. Well, harder to think about is whether his inputs can even produce a situation with more than 3 edges per vertex. My

Further, when you split a vertex and introduce a new edge, you are adding another edge+vertex to the connectivity of all the faces that connect to both sides of the split. It is more likely than not that they are no longer planar (assuming the vertex generated in a split

Looking back to my own derivation for triangle-based hulls (which I'm sure is flawed in some way), at first I thought I had a problem by starting with a tetrahedron, which satisfies Vorpy's target of 3 edges per vertex. I thought that my induction-based argument might not permit triangle-fans to develop and therefore might not have produced a tight upper bound on the # of edges. But, in face, it does permit triangle-fans....simply subdivide an edge, then subdivide the two edges that result, and so-on. A triangle-fan is produced at the opposite vertex. I am certain that there's some other fatal flaw in my logic, but I don't yet see it.

I'm enjoying this discussion, Vorpy, and if there is something I'm missing about your argument, I would love to hear it!

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 11 February 2008 - 06:16 AM

Quote:

Original post by alvaro

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

A tetrahedron breaks that formula. Did you mean to use a different one?

G = 3 exactly

V = 4

E = 6

G*V = 3*4 = 12

E/2 = 6/2 = 3

But 12 != 3

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 11 February 2008 - 01:14 PM

I think we might be trying to solve two or three different problems.

Alvero's formula can be fixed by multiplying instead of dividing by two. It should be G*V = E*2.

In my solution, I'm talking about convex polyhedrons in general, where a face can have any number of sides. I am also trying to find a least upper bound for the number of vertices in the set of all possible N sided convex polyhedra. For any single polyhedron, the answer depends on that individual polyhedron. Requiring all faces to be divided into triangles does not affect the result because triangulating a face does not affect the number of vertices.

I tried to describe my solution using graph theory because it is easier to visualize than polyhedra. The vertices of the polyhedron correspond to nodes in the graph, the edges correspond to edges, and the faces correspond to regions (one of the faces corresponds to the region that is "outside" the graph).

There are some mathematical theories that every convex polyhedra has a corresponding planar, 3 connected graph, and vice versa. So it's possible to just work with the 3 connected planar graphs instead of polyhedra to find the solution. The problem is then: What is the maximum number of vertices a planar 3 connected graph with N regions can contain?

As I described above, working with the graphs, you can always split vertices with more than four edges to get a new planar 3 connected graph with the same number of regions and more vertices.

Alvero's formula can be fixed by multiplying instead of dividing by two. It should be G*V = E*2.

In my solution, I'm talking about convex polyhedrons in general, where a face can have any number of sides. I am also trying to find a least upper bound for the number of vertices in the set of all possible N sided convex polyhedra. For any single polyhedron, the answer depends on that individual polyhedron. Requiring all faces to be divided into triangles does not affect the result because triangulating a face does not affect the number of vertices.

I tried to describe my solution using graph theory because it is easier to visualize than polyhedra. The vertices of the polyhedron correspond to nodes in the graph, the edges correspond to edges, and the faces correspond to regions (one of the faces corresponds to the region that is "outside" the graph).

There are some mathematical theories that every convex polyhedra has a corresponding planar, 3 connected graph, and vice versa. So it's possible to just work with the 3 connected planar graphs instead of polyhedra to find the solution. The problem is then: What is the maximum number of vertices a planar 3 connected graph with N regions can contain?

As I described above, working with the graphs, you can always split vertices with more than four edges to get a new planar 3 connected graph with the same number of regions and more vertices.

\/ \__/

/\ becomes / \

Posted 11 February 2008 - 01:51 PM

Quote:

Original post by Vorpy

I think we might be trying to solve two or three different problems.

Agreed! I hope one of them is the answer to samgzman's.

Quote:

Original post by VorpyI tried to describe my solution using graph theory because it is easier to visualize than polyhedra. The vertices of the polyhedron correspond to nodes in the graph, the edges correspond to edges, and the faces correspond to regions (one of the faces corresponds to the region that is "outside" the graph).

There are some mathematical theories that every convex polyhedra has a corresponding planar, 3 connected graph, and vice versa. So it's possible to just work with the 3 connected planar graphs instead of polyhedra to find the solution. The problem is then: What is the maximum number of vertices a planar 3 connected graph with N regions can contain?

As I described above, working with the graphs, you can always split vertices with more than four edges to get a new planar 3 connected graph with the same number of regions and more vertices.

\/ \__/

/\ becomes / \

Its interesting to think about geometry as a graph, and it does seem to be helpful to solve problems sometimes. I don't have any formal training in graph theory, though I'm familiar with the concept of duality and have coded and used the winged-edge-data-structure pretty extensively for mesh decimation and shape representation. I tend to find it easier (for myself) to think about this stuff in terms of geometric operations. I appreciate having multiple viewpoints, perspectives, and approaches here!

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 11 February 2008 - 05:36 PM

Quote:

Original post by Vorpy

I think we might be trying to solve two or three different problems.

Alvero's formula can be fixed by multiplying instead of dividing by two. It should be G*V = E*2.

Yes, that was careless typing. Sorry.

The rest of the proof should still hold.

Posted 14 February 2008 - 05:41 AM

Quote:

Original post by samgzman

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.

The solution to this comes from cyclic polytopes, and McMullen's Lower bound theorem in dual form (Google, read some papers, dig around). If I reduced the general d-dimensional cases down properly, then the answer is that for a 3 dimensional convex polytope with n faces, the maximal number of vertices is 2(n-2).

This maximum is achieved using cyclic polytopes: on the curve parameterized by (t,t^2,t^3) in space, pick q distinct points, and take the convex hull. This has q vertices and n faces, where q=2(n-2).

Even though your modified question uses pairs of parallel planes to define the polytope, you can still construct *any* polytope with such methods, so you can construct the cyclic ones, so this is precisely the bound you seek.

Chris Lomontwww.lomont.org