Method

Every packing on this site was found the same way: each piece starts as a soft, rounded body that is sharpened into the solid while pressure shrinks the container, a search then hops between arrangements, and the best one is tightened, given a small clearance and proved valid in exact arithmetic. This page explains each step and links the code that does it, so the method can be reused for other solids and containers.

The problem

For a container solid A, a piece solid B and a number n, find the smallest scale s such that n copies of B, free to translate and rotate, fit inside s·A with pairwise disjoint interiors. Pieces and containers are fixed canonical solids, so

s(A, B, n) = size of the container ÷ size of each piece.

For solids with all edges equal (Platonic and Archimedean solids, regular prisms and antiprisms) this is container edge ÷ piece edge. Catalan solids have edges of two or three lengths, so their s is the ratio of sizes of the same canonical solid (defined below); Catalan solids are only packed in themselves.

The site tracks 55 problems for n = 2–40, 2,145 cases in all:

Platonic (9): each Platonic solid in itself, and the dual pairs: cubes in an octahedron, octahedra in a cube, dodecahedra in an icosahedron, icosahedra in a dodecahedron.
Archimedean (13) and Catalan (13): each solid in itself.
Prisms and antiprisms (20): the regular triangular, pentagonal, hexagonal, octagonal and dodecagonal prisms and the square, pentagonal, hexagonal, octagonal and dodecagonal antiprisms, each in itself and in a cube. The square prism with unit edges is the cube and the triangular antiprism is the octahedron, so those cases are the Platonic problems and are not repeated.

Every value is an upper bound with a proof: the packing exists. None is claimed optimal. The only general lower bound used is the volume bound s ≥ (n · vol B / vol A)^1/3, drawn as a dashed line in every chart.

The solids

All solids are centred at the origin.

Platonic: exact unit-edge coordinates in ℚ(√2, √5), built and self-checked by solids.py.
Archimedean: the classical coordinates (permutations and sign patterns) for the eleven non-snub solids. The snub cube and snub dodecahedron are built as the orbit of one point under the rotation group, with the point chosen by Newton's method so the three Wythoff rotations move it by equal distances. All are scaled to unit edge.
Catalan: the canonical duals of the unit-edge Archimedean solids, by polar reciprocity in their common midsphere: a face with unit normal m at distance h becomes the vertex (r_m²/h)·m. Every Catalan solid has an insphere.
Prisms and antiprisms: the regular ones, with all edges equal to 1.

polyhedra.py builds the non-Platonic solids in 60-digit arithmetic, derives the faces from the convex hull and checks the vertex, edge and face counts, Euler's formula, equal edges or an insphere, planarity, and that every face plane supports the solid. The floats used by the search go to src/solids.json and 50-digit coordinates to src/solids_hp.json. Exact coordinates for the certificates are on the certification page.

Soft shapes: from balls to polyhedra

The idea comes from Yohei Nakajima's soft-to-rigid packing of unit cubes. Packing hard polyhedra directly gets stuck: sharp corners lock against each other long before the arrangement is good. Balls slide past each other easily. So every piece starts as a ball and is sharpened into the polyhedron through a family of convex shapes S_r that grows as the softness r goes to 0.

Solids with an insphere

Platonic and Catalan solids have an inscribed ball of radius ρ touching every face. For them

S_r = (1 − r/ρ)·P ⊕ B(r), 0 ≤ r ≤ ρ,

a shrunken copy of P dilated by a ball of radius r. S_ρ is the insphere, S₀ = P, every S_r lies inside P, and S_r only grows as r decreases (its support function is h_P(u) − (r/ρ)(h_P(u) − ρ), non-increasing in r because h_P ≥ ρ). So a packing of the polyhedra is a packing of every S_r, and the smallest container grows monotonically along the path: the search never has to undo anything, only make room.

Solids without one: the r-rounding

Archimedean solids, prisms and antiprisms have no ball touching every face, so the generalization uses the r-rounding

S_r = (P ⊖ B(r)) ⊕ B(r),

the union of all balls of radius r inside P. Its core P ⊖ B(r) = {x : n_f·x ≤ h_f − r} is again a polytope; faces vanish from it at finitely many values of r, and between those values every core vertex moves linearly, V(r) = V₀ + r·W. polyhedra.py precomputes these intervals ("cores"), and the simulator reads the core for any r in constant time. The r-rounding also lies inside P and grows as r decreases, and for a solid with an insphere it is exactly Nakajima's shape, so this is one homotopy, not two. The search starts at r = 0.49 in internal units, where every solid is scaled so its inradius is ½; for solids without an insphere the starting shape is a rounded body rather than a ball.

Contacts between soft shapes

Two rounded bodies K ⊕ B(r) and L ⊕ B(r) overlap exactly when their cores come closer than 2r, and the overlap depth is 2r minus the signed distance of the cores. So all contact geometry is computed on the cores, which are polytopes:

overlapping cores: the exact penetration depth by the separating axis test over the face normals of both cores and the cross products of their edges. For solids with many faces the edge pairs are pruned with the Gauss map (an edge pair can only give a face of the Minkowski difference when the arcs of the two edges on the sphere of normals cross, as in D. Gregorius, “The Separating Axis Test between Convex Polyhedra”, GDC 2013), which keeps the test exact;
disjoint cores: the exact Euclidean distance by enumerating vertex–face, face–vertex and edge–edge features, limited to the slabs between the two support planes of a separating direction.

Both come with analytic gradients with respect to the centres and the rotation vectors of the two pieces. This is src/geom.js.

Dynamics: sharpening under pressure

src/sim.js minimizes

E = Σ_pairs (2r − d_core)₊² + Σ_walls (violation)₊² + μ · (container size)

by heavy-ball descent on all centres, quaternions and the container size, with a velocity cap and annealed noise. The wall term uses the support function of S_r in each container face normal. A fresh run spends 5,000 steps compressing the soft bodies, 45,000 steps lowering r linearly to 0 and 3,000 steps settling the rigid pieces. Then the packing is legalized: centres are scaled apart until no pair overlaps, and the container is shrunk to the smallest one over all translations, a four-variable linear program (solved with a small simplex method for containers with many faces). src/server.js runs these simulations for the search engine.

The search engine

A fresh run takes 20–60 seconds and mostly re-discovers dense packings. The engine, scripts/engine.py, instead keeps an archive with the best packing and a pool of distinct good packings for every (problem, n), and repeatedly applies one move:

hop (55%): expand the best packing slightly, soften the pieces, shake them at fixed container size until their relative arrangement has changed by a random target, then re-sharpen under pressure. For larger n many hops shake only a cluster of neighbouring pieces.
fresh (15%): a full soft-to-rigid run from random balls, which keeps the archive diverse.
ascend (15%): the best (n − 1)-packing plus one piece in its largest hole, re-sharpened.
descend (10%): the best (n + 1)-packing minus the piece whose removal lets the container shrink most.
reinsert (5%): remove one to three pieces and put them back into the largest holes.

Removing a piece never makes a packing invalid, so s(n) ≤ s(n + 1) always holds, and the archive enforces it on every write: whenever the best n-packing is worse than the best (n + 1)-packing minus a piece, the latter replaces it and is queued for re-tightening. The scheduler fills every empty case first, then brings every case to a minimum number of attempts, then spends effort where it pays most per piece.

For the Archimedean, Catalan and prism families the engine ran on three kinds of machines at once: two workers in the cloud, two on a laptop in short bounded runs, and four GitHub Actions jobs of four workers each, started every hour by .github/workflows/search.yml. Remote results come back through scripts/remote.py and are re-legalized before they can enter the archive. In total the archive records 80,540 attempts.

Tightening and record files

Promising results are tightened by src/exact.py: the container size is minimized subject to hard constraints (every vertex inside every container face, and a separating plane for every nearby pair, with its normal and offset as variables), first by sequential linear programming with trust regions and then, for small n, by SLSQP. A round is accepted only if the legalized size went down, and tightening stops when 50 rounds gain less than 10⁻⁷ relative.

src/claim.py then turns the tightened packing into a record file: centres are spread until every pair has a separation of at least 10⁻⁷, the container is refitted with at least 10⁻⁷ clearance on every wall, and s is rounded up at the 13th decimal. The displayed value (“4.10646+”) is s truncated to five decimals. Record files live in records/, one folder per problem, next to their certificate and float check; the constructions page links every one.

Verification

Every record is checked twice. verify_general.py is a floating-point separating-axis check. certify_general.py is a proof: exact coordinates in number fields, exactly orthogonal rational rotations, and rigorous interval arithmetic for containment and for a separating plane between every pair. The certification page explains what it proves and how. All 2,145 records on this site are certified exactly.

Generalizing it

Nothing in the pipeline is specific to these 41 solids. To pack other convex polyhedra:

A new solid: add it to polyhedra.py (vertices in high precision; faces, checks and r-rounding cores are derived) and give its number field in scripts/exact_solids.py. Everything downstream reads src/solids.json.
A new pair: any piece can go in any container. Add the problem id to PROBLEMS in scripts/engine.py.
Mixed pieces or non-polyhedral containers (a sphere, a cylinder) need changes in the energy (src/sim.js), in the tightening constraints (src/exact.py) and in the certificate, but the homotopy itself carries over unchanged.
Other measures, such as volume ratios or a container of fixed shape but free aspect, only change the objective.

Ideas and questions are welcome as category proposals.

Code map

polyhedra.py: Archimedean, Catalan, prism and antiprism solids; faces, checks, r-rounding cores
solids.py: exact Platonic solids in ℚ(√2, √5) with self-check
src/geom.js: signed distances, penetration depths and gradients; pruned separating axis test
src/sim.js: soft-to-rigid dynamics, hops, legalization, container LP
src/server.js: JSON-lines compute server used by the engine
scripts/engine.py: basin-hopping search, monotone archive, scheduler
src/exact.py: sequential LP and SLSQP tightening, legalization
src/claim.py: record files with explicit clearance
verify_general.py: floating-point check of any record
certify_general.py: exact certificate of any record (standard library only)
algebraic.py: number fields, Sturm sequences, rational interval arithmetic
scripts/exact_solids.py: exact coordinates of every solid by PSLQ, proved by self-check
certify_exact.py: the original certifier for Platonic records, over ℚ(√2, √5)
scripts/publish.py: records, certificates, tables and this site from the archive
scripts/site.py: builds this website from web/ and the records
scripts/check_submission.py: checks and accepts packings submitted through GitHub issues
test/: test suite: gradients, optimality conditions, broken files that must be rejected

Reproduce

git clone https://github.com/alejandrozu/platonic-packing.git && cd platonic-packing
pip install numpy scipy mpmath sympy        # Node ≥ 18 for the simulator
python3 certify_general.py records/phcinphc/phcinphc_n12.json   # check one record exactly
nohup setsid scripts/run_forever.sh > logs/supervisor.out 2>&1 &   # run the search (resumes from state/best)
python3 scripts/engine.py status                                    # current table
touch state/STOP                                                    # stop gracefully
python3 scripts/publish.py --no-push                                # records, certificates, site