Optimization challenges

Visualize and submit solutions to optimization problems, and compete on the leaderboards.

Constellation Packing

Pack 100 rigid groups of circular dots into the smallest circle centered at the origin.

Each constellation is a rigid group of 5 circular dots. The 5 dots in a constellation all have the same radius. Different constellations may have different radii. You may rotate and move each constellation, but you may not change its shape. Dots from different constellations may touch, but they may not overlap. Every dot must fit inside a circle centered at the origin. Make this circle as small as possible. The enclosing radius must not be greater than 75. This prevents solutions with very distant constellations.

An observatory dome beneath a star-filled night sky.
Show mathematical formulationHide mathematical formulation
Constellation \(i\) has dot centers \(p_{ij}\) and dot radius \(r_i\). Choose an angle \(\theta_i\) and a translation \(t_i\), giving \(q_{ij}=\operatorname{Rot}(\theta_i)p_{ij}+t_i\). Dots from different constellations must satisfy \(\lVert q_{ij}-q_{k\ell}\rVert\ge r_i+r_k\) for \(i\ne k\). Minimize \(\rho=\max_{i,j}(\lVert q_{ij}\rVert+r_i)\), with \(\rho\le75\). Comparisons use an absolute tolerance of \(10^{-7}\) (1e-7).

Instance: The instance contains 100 constellations with 5 dots each. Each constellation lists its dot radius, between 0.8 and 1.6, followed by the 5 dot centers in local coordinates.

Show data formatHide data format 
RULES constellationCount dotsPerConstellation minDotRadius maxDotRadius overlapTolerance maxContainerRadius

CONSTELLATIONS count
  index radius x0 y0 x1 y1 x2 y2 x3 y3 x4 y4

Indices are zero-based. Coordinates and radii are real numbers.
Lines beginning with # are comments.
Download data (txt) Download local scorer

Solution format: Give exactly 100 non-empty lines, in constellation index order: `angleRadians tx ty` The first line places constellation 0, the second line places constellation 1, and so on. Angles are in radians. Every value must be a finite real number.

Scoring: \(\text{Score}=\rho=\max_{i,j}\left(\left\lVert \operatorname{Rot}(\theta_i)p_{ij}+t_i\right\rVert+r_i\right)\) Smaller is better. The score is the radius of the circle centered at the origin that contains every placed dot. Touching is allowed. A solution is invalid if dots from different constellations overlap or if the radius is greater than 75.

Solution example: Download example