A short proof of rigidity of convex polytopes.
Consider games where players wish to minimize the cost to reach some state. A subgame-perfect Nash equilibrium can be regarded as a collection of optimal paths on such games. Similarly, the well-known state-labeling algorithm used in model checking can be viewed as computing optimal paths on a Kripke structure, where each path has a minimum number of transitions. We exploit these similarities in a common generalization of extensive games and Kripke structures that we name “graph games”. By extending...
We present a constructive proof of Alexandrov’s theorem on the existence of a convex polytope with a given metric on the boundary. The polytope is obtained by deforming certain generalized convex polytopes with the given boundary. We study the space of generalized convex polytopes and discover a connection with weighted Delaunay triangulations of polyhedral surfaces. The existence of the deformation follows from the non-degeneracy of the Hessian of the total scalar curvature of generalized convex...
The paper gives an illustrated introduction to the theory of hyperbolic virtual polytopes and related counterexamples to A.D. Alexandrov’s conjecture.
Let be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is ; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.
In 1970, E.M.Andreev published a classification of all three-dimensional compact hyperbolic polyhedra (other than tetrahedra) having non-obtuse dihedral angles. Given a combinatorial description of a polyhedron, , Andreev’s Theorem provides five classes of linear inequalities, depending on , for the dihedral angles, which are necessary and sufficient conditions for the existence of a hyperbolic polyhedron realizing with the assigned dihedral angles. Andreev’s Theorem also shows that the resulting...