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 instinct tells me it is possible, but I am not sure. (I'm thinking about a sequence of n plane pairs, all rotated slightly and translated such that there are many plane/plane intersections that come together at a point....with arbitrary input plane pairs, I think its possible.)

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 is colinear with one of the pre-split edges). If the hull is required to be made of only 3 node triangles (this being games/graphics forum an all), then you'd have to triangulate the newly nontriangle faces, which would increase the face count, often the plane count. So, the rule about being able to increase edge/vertex count without increasing faces is dependent on being able to deal with non-triangles. But, again, I do not know samgzman's requirement.

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!

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

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!

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.