RECONSTRUCTING POLYTOPES VIA CAUCHY RIGIDITY: II

Octavia Petrovici

My work follows that of Biliana Kaneva, described on the previous page. To use our approach for folding polytopes, the relaxation algorithm must work for polytopes with thousands of edges. Experiments showed that our first version would not reliably converge for polytopes of 50 or more vertices. I improved the algorithm, which is a gradient descent with barriers, by revising our method for implementing the barriers – reflex edges or dents in the polytope. After this and other improvements, I showed that the algorithm converged on large examples. One is shown in Figures 1 and 2. Figure 1 shows an initial polytope of 1698 edges. The edge lengths have been stretched to be systematically wrong. After ten hours of computation time, the polytope relaxed to its correct nearly spherical shape, shown in Figure 2; the maximum edge length error is 1 percent.

Having demonstrated that a good starting position leads to convergence, we turned to guaranteeing a convex starting polytope. A literature search turned up research in Australia on just this problem. We obtained their code from the University of Newcastle, and I interfaced it to our Cauchy code. Figure 3 shows the pyramid-like shapes it produces; in this case, for a 100-vertex planar graph.

I plan to continue this research in the fall. (Supported by Schultz Foundation)

Figure 1. Start Polytope. Figure 2. End Polytope.

Figure 3. Pyramidal Polytope

Advisor: Joseph O’Rourke