Computing symmetry groups of polyhedra

Abstract

Knowing the symmetries of a polyhedron can be very useful for the analysis of its structure as well as for practical polyhedral computations. In this note, we study symmetry groups preserving the linear, projective and combinatorial structure of a polyhedron. In each case we give algorithmic methods to compute the corresponding group and discuss some practical experiences. For practical purposes the linear symmetry group is the most important, as its computation can be directly translated into a graph automorphism problem. We indicate how to compute integral subgroups of the linear symmetry group that are used for instance in integer linear programming.

20 pages, 1 figure; containing a corrected and improved revision

References in corpus (8)

• Lectures on 0/1-polytopes
• PALP: A Package for Analyzing Lattice Polytopes with Applications to Toric Geometry
• On the Classification of Reflexive Polyhedra
• Algorithms for Highly Symmetric Linear and Integer Programs
• Complexity and algorithms for computing Voronoi cells of lattices
• Classification of eight dimensional perfect forms
• The isometries of the cut, metric and hypermetric cones
• Smoothness and singularities of the perfect form and the second Voronoi compactification of ${\mathcal{A}}_g$

Cited by in corpus (10)

• The complete classification of five-dimensional Dirichlet-Voronoi polyhedra of translational lattices
• Iso Edge Domains
• Classification of Affine Symmetry Groups of Orbit Polytopes
• Normal forms of convex lattice polytopes
• Computing characteristic polynomials of hyperplane arrangements with symmetries
• Dragging the roots of a polynomial to the unit circle
• Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
• Equivalence of Lattice Orbit Polytopes
• Symmetry Detection for Quadratically Constrained Quadratic Programs Using Binary Layered Graphs
• Moduli of polarized Enriques surfaces -- computational aspects