An Inequality for Circle Packings Proved by Semidefinite Programming

2002/05/27 by Pablo A. Parrilo, Ronen Peretz
Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Advanced Optimization Algorithms Research #Robotic Mechanisms and Dynamics #math.AG #math.OC

paper · pdf · doi:10.1007/s00454-003-2880-2

published as Discrete and Computational Geometry, Vol. 31, No. 3, 2004. · 11 pages, submitted

arxiv created 2002/05/27 · openalex publication_date 2004/02/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 particular 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.

Citations

• Semidefinite programming relaxations for semialgebraic problems
• Symmetry groups, semidefinite programs, and sums of squares

Related

• An algebraic approach to circle packing
• The circle packing problem: a theoretical comparison of various convexification techniques
• Computing Circle Packing Representations of Planar Graphs
• A circle packing proof of the Combinatorial Riemann Mapping Theorem
• Balanced Circle Packings for Planar Graphs