An Inequality for Circle Packings Proved by Semidefinite Programming Academic Article uri icon


  • A geometric inequality among three triangles, originating in circle packing problems, is introduced. In order to prove it, we reduce the original formulation to the nonnegativity of a polynomial in four real indeterminates. Techniques based on sum of squares decompositions, semidefinite programming and symmetry reduction are then applied to provide an easily verifiable nonnegativity certificate.

publication date

  • January 1, 2004