Rectangle Construction Search Lab

Search

Target n: Search iterations:

The search starts with a random construction and repeatedly modifies it. A modification is kept when it improves the objective, with occasional random moves to escape local minima.

Current construction

r(n)

D · I = 0
√n = —
√(n / log₂ n) = —
r / √n = —
r / √(n / log₂ n) = —

Experimental graph

best construction r(n)

√n

√(n/log₂ n)

The red curve consists only of constructions the computer has actually found. It is therefore an experimental upper bound on the true r(n).

Manual construction

Draw: drag on empty space.
Move: drag inside rectangle.
Resize: drag a corner.
Delete: select and press Delete.

Sweep line

Show vertical line x =

Useful for experimenting with your R₀, R_L, R_R decomposition.

Display

Grid Highlight maximum intersecting family Highlight maximum disjoint family Touching counts as intersection

What am I looking for?

For a construction with n rectangles:

D = largest pairwise-disjoint subfamily.
I = largest pairwise-intersecting subfamily.
r(n) = the minimum possible max(D,I).

The program cannot prove that its construction is optimal. Instead, if it finds a construction with

max(D,I) < √n

then it gives a concrete counterexample to the claim r(n) ≥ √n.