An inequality for circle packings proved by semidefinite programming

DOI10.1007/S00454-003-2880-2MaRDI QIDQ701787zbMATH OpenOpenAlexFDO

Authors Pablo A. Parrilo, Ronen Peretz

Publication date 16 December 2004

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

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

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)

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.

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

Cited in

(5)

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

Describes a project that uses

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)