P15 · Packing and covering · Classic

Spreading points in the unit square

1y0
0x1
VERIFIED CONSTRUCTIONthe closest pair
n = 6Current record · open

Place n points in the unit square, maximizing the smallest distance between any two of them.

Formal definition

  • ContainerThe unit square: the origin (0, 0) at its lower-left corner, (1, 1) at its upper right
  • SubmissionExactly n points, no two coinciding
  • ConstraintsEvery point lies inside the square or on its boundary
  • ObjectiveMake the smallest pairwise distance as large as possible; compared internally by its square, exactly

Getting a feel for it

Where the room for improvement is

Spreading points IS packing equal circles: discs of half the minimum distance around each point must not overlap. Optima are jammed contact structures, and the container shape decides everything.

Where the frontier is

Spreading points in a square is dual to packing equal circles in one; proofs in the csq table transfer. n = 2, 4, 5 and 9 are proven here by elementary arguments, and the rest follow csq's progress.

Source
ONE LEADERBOARD PER n

Current best solutions by n

Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.