An inequality for circle packings proved by semidefinite programming

DOI10.1007/S00454-003-2880-2zbMATH Open1059.51020arXivmath/0205278OpenAlexW2001263356MaRDI QIDQ701787FDOQ701787

Authors: Pablo A. Parrilo, Ronen Peretz 

Publication date: 16 December 2004

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0205278

Recommendations

• scientific article; zbMATH DE number 1745034
• A mechanical proof to a geometric inequality of Zirakzadeh through rectangular partition of polyhedra
• A semidefinite programming hierarchy for packing problems in discrete geometry
• Publication:5751975
• A circle packing algorithm

zbMATH Keywords

semidefinite programminginequalitysums of squarescircle packings

Mathematics Subject Classification ID

Semidefinite programming (90C22) Inequalities and extremum problems in real or complex geometry (51M16) Sums of squares and representations by other particular quadratic forms (11E25) Circle packings and discrete conformal geometry (52C26)

Cited In (5)

• A mechanical proof to a geometric inequality of Zirakzadeh through rectangular partition of polyhedra
• The Schwarz-Pick lemma for circle packings
• Computing sum of squares decompositions with rational coefficients
• A New Verified Optimization Technique for the "Packing Circles in a Unit Square" Problems
• Addendum to our paper The Schwarz-Pick lemma for circle packings

Uses Software

• SeDuMi

This page was built for publication: An inequality for circle packings proved by semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q701787)