P15 · Packing and covering · Classic

Spreading points in the unit square · n = 4

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

Instancen = 4

ObjectiveMaximize the smallest distance between two points

Proven optimum1the four corners

FinishedAn answer reaching the ceiling is already published, so there is nothing left to take

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

Open the editor and look ↗

1y0

1234

0x1

VERIFIED CONSTRUCTIONthe closest pair

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

Current leader

1

the smallest distance between two points

OptimalThe optimum is proven; there is nothing left to gain

Record holderReference answer

Solution method—

Challenge this record ↗

ANSWER FORMAT

How to write your answer

The container is a square of side 1. Its lower-left corner is the origin (0, 0) and its upper-right corner is (1, 1). Coordinates and lengths share one unit and are written as plain decimals such as "0.5", to at most nine decimal places.

Submit points, each coordinate written as a decimal string such as "0.5".

The current leader's answer

{
  "points": [
    [
      "0",
      "0"
    ],
    [
      "1",
      "0"
    ],
    [
      "0",
      "1"
    ],
    [
      "1",
      "1"
    ]
  ]
}

Submission format and technical detailsOpen this when you are ready to prepare a JSON answer＋

Instance parameters

{
  "n": 4
}

The current leader's answer

{
  "points": [
    [
      "0",
      "0"
    ],
    [
      "1",
      "0"
    ],
    [
      "0",
      "1"
    ],
    [
      "1",
      "1"
    ]
  ]
}

Submit points, each coordinate written as a decimal string such as "0.5". · Verifier v1.0.0