Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The notion of derived polygon is natural and leads to remarkable convergence. Start with a polygon, and replace it by locating a point on every edge a fraction $\alpha$ between the two endpoints. For example, here is what happens for a random polygon of $8$ vertices and $\alpha=\frac{1}{4}$ (successive images rescaled):
          DerivedPolygons3x5

MathWorld: "the derived polygons ... approach a shape with opposite sides parallel and equal in length, and all have the same centroid."

Now imagine generalizing this to polyhedra, let's say, convex polyhedra in $\mathbb{R}^3$ with triangular faces. Start with a polyhedron $P$ of $F$ faces and $V$ vertices. For a given triple of positive reals $(\alpha,\beta,\gamma)$ that sum to $1$, locate a point $p$ in each face by weighting the face's three vertices by $(\alpha,\beta,\gamma)$. (So if $\alpha=\beta=\gamma=\frac{1}{3}$, $p$ is the centroid of the face.) Now replace the original polyhedron $P$ by the convex hull of the new points. Here is an example with $(\frac{1}{4},\frac{1}{2},\frac{1}{4})$ (again, each image rescaled):
          DerivedPolyhedra5x2
You can see what happens. At first $V=8$ and $F=10$, but next $V=10$ (because every face generates a point), and by Euler's formula, $F=16$ ($F=2 V-4$). Etc.: the number of vertices and faces grows. Here are enlargements of the first and 10th polyhedra, the latter of which has $1540$ vertices:
 BegEndPolyhedra
It seems that, despite the combinatorial growth in $\mathbb{R}^3$ absent in $\mathbb{R}^2$, it is likely the shape is converging to a limit that may bear similarities to what can be established in 2D. My question is:

Q. Has this process been studied before? If so, does the shape approach a limit largely independent of $(\alpha,\beta,\gamma)$, analogous to the situation in 2D? If so, what characteristics does this limit shape bear to the initial polyhedron?

share|improve this question
3  
How do you order the points of the triangles? Do you use all six orders? –  Lev Borisov Nov 24 '13 at 13:14
    
@LevBorisov: Good point, Lev. I am just using one, random order. Probably using the centroid is the cleanest rule. –  Joseph O'Rourke Nov 24 '13 at 14:00
1  
It is an interesting setup, maybe some people in probability have looked at it. There is certainly some discontinuity in the process, even if you look at centroids, because the new polytope will depend discontinuously on the original one. Still, there is probably some finite dimensional space of limiting shapes with probability 1, at least locally. –  Lev Borisov Nov 24 '13 at 14:24
1  
It's not so far off from talks I've seen by Tony DeRose of Pixar, where the limit mesh is used as a model in animation. Old papers are at homes.cs.washington.edu/~derose/papers.html , and probably one can watch a talk on the MSRI website, msri.org/general_events/20258 –  Allen Knutson Nov 24 '13 at 15:47
1  
Did you try "polyhedra" with intersecting faces as in the example for a polygon? Could you provide a picture just to see what happens? Is the obtained polyhedron going "back to normal"? –  Olga Nov 28 '13 at 8:18
show 2 more comments

2 Answers

What you call the derived polygon is a construction that has appeared many times in literature. I believe the first occurrence was in a 1878 paper by Darboux, "Sur un problème de géométrie élémentaire", but it has also been a topic of many problems and articles in the American Mathematical Monthly, which is where I've learned about it. :-)

Not only is the limiting shape a polygon with opposite sides parallel, but it is in fact the affine image of a regular $n$-gon (phrased this way you don't have to restrict to even number of sides). The proof boils down to the fact that every polygon is a linear combination of regular polygons, and these are eigenvectors of the associated circulant matrix. One, then observes that the limiting shape is determined by looking at the two largest eigenvalues. This is nicely explained in a monthly article, "A Polygon Problem", by E. R. Berlekamp, E. N. Gilbert and F. W. Sinden.

Another interesting perspective is to think of the limiting shape as equally distributed points on an ellipse. This, in fact, makes an analogy with the continuous version of the problem. If you have a curve in $\mathbb R^2$ and want to consider a second order parabolic evolution equation which is invariant under affine transformations, you will be studying a flow called the affine normal flow. In "Contraction of convex hypersurfaces by their affine normal", Ben Andrews proves that the affine normal flow contracts every convex hypersurface to a point, and if you scale the limiting shape accordingly, the shape converges to an ellipsoid. In fact the midpoint iteration from before is just the discrete analog of this evolution for 2D curves!

Now, coming to your question about the 3 dimensional polytopes. Your discrete evolution is clearly invariant under affine transformations and should approximate a second order evolution equation, which would then coincide with the affine normal flow. Since in dimensions higher than two, the mesh becomes more refined in every iteration, the limiting surface should in fact converge to the ellipsoid, instead of just a discrete approximation of it as in the 2D case. Unfortunately I do not know enough about numerical analysis or differential geometry to tackle this problem, and just gave a heuristic answer. If you add those tags perhaps an expert will explain how to prove a result like this.

share|improve this answer
    
"the limiting surface should in fact converge to the ellipsoid": Very nice hypothesis! –  Joseph O'Rourke Nov 25 '13 at 12:19
add comment

Just a bit more "data" in the form of images. I started with a "random polyhedron" built from the convex hull of a small number of points. Then I iterated the process of replacing each face by its centroid, i.e., $\alpha=\beta=\gamma=\frac{1}{3}$ in my original description, and again taking the convex hull. At least visually, the data support Gjergji's suggestion that the process converges to ellipsoids (of different axes lengths).
   CentroidPolyhedra
So, to make an explicit conjecture out of these observations:

Conjecture. Given any convex polyhedron $P$ in $\mathbb{R}^3$, let $c(P)$ be the convex hull of the centroids of the faces of $P$. Then $c^k(P)$ converges to an ellipsoid as $k \to \infty$.

Secondarily, it makes sense to conjecture the same holds for any convex polytope $P$ in $\mathbb{R}^d$.

share|improve this answer
1  
Yes the same argument leads to the conjecture for arbitrary dimensions. The hard part would be to justify that in the limit this process becomes a smooth evolution of hypersurfaces, because then the result would follow from the papers mentioned in my answer. –  Gjergji Zaimi Nov 27 '13 at 0:48
1  
@GjergjiZaimi: I "conjecture" that this already is a theorem; or---if not---soon will be! –  Joseph O'Rourke Nov 27 '13 at 0:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.