Uniform sampling in a square: equality classification for triangular lattices and exact optimization of staggered rows

Abstract

For n points in the unit square, consider M=2h/δ, where h is the covering radius and δ the minimum separation. We prove M≥2/√3 for every n≥5, with equality forcing a complete triangular-lattice window. For n≥10 the lattice must be aligned with the square, giving a complete classification of equality cardinalities by two integer inequalities. We also derive an exact objective function and three optimization regimes for a staggered rectangular family. These results settle the continuous optima of P56 at n=7,8,14,20,22,23,30. They do not determine the unrestricted optima at n=33,35 or at arbitrary n.

Download complete manuscript (Markdown) ↓

1. Problem, scope and related work

Let Q=[0,1]² and let P⊂Q contain n distinct points. Define the quantities below; Mₙ initially ranges over real coordinates, without the site's decimal restriction.

δ(P)=min{‖p−q‖: p,q∈P, p≠q}; h(P)=max{x∈Q} min{p∈P} ‖x−p‖; M(P)=2h(P)/δ(P); Mₙ=inf{|P|=n} M(P).

This is the gap ratio between covering and separation. Some mesh-ratio conventions use h/δ, differing by a factor of two. Here a honeycomb layout means a triangular lattice of sites with hexagonal interior Voronoi cells, not sites at the vertices of a honeycomb graph.

Bishnu et al. [1] study gap ratio in continuous and discrete spaces; their square lemma gives a finite-cardinality lower bound tending to 2/√3. Teramoto et al. [2] study online insertion, a different problem from offline optimization here. Bondarenko, Hardin and Saff [3] study mesh ratios of best-packing and Riesz-energy configurations. Our focus is equality rigidity in a finite square, boundary compatibility and an exactly optimizable row family. This is a self-published research manuscript, not externally peer reviewed; no priority or first-discovery claim is made.

The optimum is attained for every n≥2. In a nonempty sublevel set M≤U, coverage by n discs of radius h gives 1≤nπh² and hence δ≥2/(U√(nπ)). This sublevel set stays uniformly away from collisions in the compact space Qⁿ. Continuity of h and δ gives a minimizer. Consequently, excluding equality below implies a strict inequality for the optimum, not merely nonattainment of an infimum.

2. A Voronoi boundary-connectivity lemma

Lemma. If h<1/2 and δ>√2h, each clipped Voronoi cell Vₚ has connected intersection with ∂Q. The graph G formed by all non-container Voronoi edges and their endpoints is connected, and its vertices on the container boundary have degree one.

Proof. Every point of Vₚ is within h of p, so its diameter is at most 2h<1: it cannot meet opposite walls. If it meets two adjacent walls, move these to the coordinate axes and write p=(u,v), with 0≤v≤u≤h after exchanging axes. Suppose another site q has distance s≤r=√(u²+v²) from the corner. Its coordinates are nonnegative, so p·q≥v(qₓ+qᵧ)≥vs.

‖p−q‖²≤r²+s²−2vs≤max{r²,2r(r−v)}≤2u²≤2h²<δ².

The middle inequality maximizes a convex quadratic on [0,r]; the last uses r²≤2u² and r(r−v)=u²+v²−rv≤u². Thus p is the unique nearest site at the corner. Convexity joins the two wall intervals through that corner. The non-container boundary of each cell is therefore a connected arc, including its endpoints, or a closed loop.

Connect two interior points of G by a generic path inside Q. Replace each passage through a cell by a path on its non-container boundary; this yields a path in G. Boundary endpoints connect to the interior along their incident edges. Three nearest sites at a wall point lie in one semicircle, forcing a pair with central angle at most 90° and δ≤√2h. At a corner even two nearest sites are impossible. Boundary graph vertices consequently have degree one. We use the geometric Voronoi graph, without artificial vertices subdividing straight edges. ∎

3. Finite-cardinality lower bound and equality rigidity

Theorem 1. For every n≥5, Mₙ≥2/√3. If equality holds, there is a triangular lattice Λ of nearest-neighbour spacing δ such that P=Λ∩Q.

Proof. It suffices to consider M≤2/√3. Partition Q into four smaller squares, assigning shared-boundary points to one part. Pigeonhole gives δ≤1/√2. Hence h≤1/√6<1/2 and δ>√2h, so the lemma applies. G must have an interior vertex: otherwise its components are straight boundary-to-boundary chords; connectivity permits only one chord and two cells, contradicting n≥5.

At an interior vertex at least three nearest sites lie on a circle of radius R≤h. One central gap is at most 120°, so δ≤√3R≤√3h, proving the bound. At equality there are exactly three sites, all central gaps are 120°, and R=h: they form an equilateral triangle of side δ. Four sites would force δ≤√2h and are impossible.

Connectivity and degree-one boundary endpoints connect all interior vertices by interior edges. Every edge has an interior endpoint, or it would be a separate chord component. Every cell has a non-container edge, so every site belongs to an interior triangle. Adjacent interior vertices give equilateral triangles sharing a δ-edge, with third vertices on opposite sides. A single triangular lattice propagates throughout G to all sites. A missing site q∈(Λ∩Q)∖P would have distance at least δ>h from P, contradicting coverage. Thus P=Λ∩Q. ∎

4. Exact formula for staggered rectangular arrays

Take integers K≥L≥1, K≥2, a phase e∈{0,1}, and 1≤t≤K/L. The following array has symmetric top and bottom margins; t controls its aspect ratio.

a=1/K, b=t/K, m=(1−Lb)/2; P(K,L,e,t)={(ia,m+jb): 0≤i≤K, 0≤j≤L, i+j≡e (mod 2)}.

N(K,L,e)=((K+1)(L+1)+(−1)ᵉ)/2 if K,L are even; otherwise N(K,L,e)=(K+1)(L+1)/2.

Theorem 2. Its separation, covering radius and objective are as follows. The objective is independent of phase, although the cardinality may not be.

δ=a min{2,√(1+t²)}; h=a max{(1+t²)/(2t),√(1+(K−Lt)²/4)}; M=2 max{(1+t²)/(2t),√(1+(K−Lt)²/4)}/min{2,√(1+t²)}.

Proof. Candidate shortest vectors have lengths 2a, √(a²+b²), and 2b. Since b≥a and the finite array contains pairs of the first two kinds, this gives δ. The infinite array has elementary triangles of base 2a and height b, with circumradius R=(a²+b²)/(2b). For b≥a these form a Delaunay triangulation (with cocircular degeneracy at b=a): the angle opposite a horizontal edge is 2 arctan(a/b)≤90°, and that opposite a sloping edge is arctan(b/a)<90°, so adjacent opposite angles sum to at most 180°. Circumcentres lie inside or on these triangles, and the empty-circle radius is R.

Reflection across each side of B=[0,1]×[m,1−m] preserves the infinite array. Folding a nearest lattice site into B does not increase its distance to a given point of B, so B is covered with radius R. Each phase contains a full elementary triangle in B, attaining R. The outer bands are within C=√(a²+m²) of the extreme row. At a bottom-wall column missing from that row, the horizontal neighbours are exactly C away, while subsequent rows are at distance at least m+b≥C. Thus C is attained as well, and h=max{R,C}. ∎

5. Three family-optimal regimes

Corollary 2.1. Fix K,L,e and optimize t only within this family. A: if K/L≤√3, the array is height-limited and t*=K/L, M*=√(1+(L/K)²). B: if √3L≤K≤√3L+2/√3, take t*=√3 and M*=2/√3. C: if K>√3L+2/√3, t* is the unique root in (√3,K/L) of the following equation.

(t+1/t)/2=√(1+(K−Lt)²/4); (L²−1)t⁴−2KLt³+(K²+2)t²−1=0; M*=(t*+1/t*)/2.

Proof. For t≤√3, the interior term divided by separation is √(1+t²)/(2t), strictly decreasing. The boundary term has decreasing numerator and increasing denominator, so also decreases. For t≥√3, separation stays at 2a; the interior term increases and the boundary term decreases. The minimum is therefore at the allowed endpoint, at √3, or at their unique crossing, giving A, B and C. ∎

For example, (K,L,e)=(9,5,0) attains the global optimum at n=30; (10,5,0) gives the family value (7√31−25)/12≈1.164529211651 at n=33; and (9,6,0) gives √13/3≈1.201850425155 at n=35. The latter two are family optima, not lower bounds against arbitrary deformations of the sites.

6. Equality lattices must align when n≥10

Lemma. For n≥10, an equality lattice has a family of lines parallel to a square side. The proof excludes nonzero angles analytically, without a numerical scan. Combining 90° square symmetry, 60° lattice symmetry and reflection reduces the angle to 0≤θ≤15°. Suppose θ>0, normalize δ=1, and put r=1/√3. Extend the finite window to all lattice sites in x≥0; this only improves left-wall coverage.

a⃗=(cos θ,sin θ), b⃗=(cos(60°+θ),sin(60°+θ)), A=cos θ, c=cos(60°+θ), p=√3/2.

The j-th line parallel to a⃗ meets the wall at height Yⱼ, with successive intercepts p/A apart. Its first site in the half-plane has 0≤xⱼ<A and yⱼ=Yⱼ+xⱼtanθ, with xⱼ₊₁≡xⱼ+c (mod A). Since A>r, only this site can serve the wall. Its interval is Iⱼ=[yⱼ−√(r²−xⱼ²),yⱼ+√(r²−xⱼ²)], empty when xⱼ>r.

In a non-wrapping step the centres differ by b⃗ and are one unit apart. Their radius-r lens has leftmost coordinate xⱼ+c/2−sin(60°+θ)/(2√3)=xⱼ−sinθ/√3. Their wall intervals overlap exactly when xⱼ≤sinθ/√3. The leftmost lens point really is a circle intersection: a disc's left horizontal extremum is outside the other disc, since cos(60°+θ)<√3/2; the rightmost lens coordinate is positive.

In a wrapping step put x′=xⱼ₊₁≥0. The corresponding lens begins at x′+sinθ/√3>0, so the wall intervals cannot overlap. Two consecutive overlapping non-wrapping steps are also impossible: they would require xⱼ+c≤sinθ/√3, whereas c−sinθ/√3=(√3cosθ−5sinθ)/(2√3)>0 because tanθ≤2−√3<√3/5 (the final comparison reduces to 100<108).

Centres at least two rows apart have vertical separation at least √3/cosθ−sinθ≥√3−1/2>2/√3=2r, so nonadjacent rows cannot connect. The interval family is locally finite; each connected covered component contains at most two discs and has length at most sin(60°+θ)+r+√(r²−c²). Since cos75°>1/4, this is strictly below 1+1/√3+√39/12<101/48; the rational estimates follow from 48<49 and 16·39<625. Single-disc components satisfy the same bound.

Restoring scale, each covered component has length below 101δ/48. With n≥10, a 3×3 partition gives δ≤√2/3, so this length is below 101√2/144<1, since 20402<20736. A covered unit wall must lie in a single connected component, a contradiction. Hence θ=0. ∎

7. Complete integer classification of equality cardinalities (n≥10)

Theorem 3. For n≥10, Mₙ=2/√3 if and only if integers K≥2, L≥1 and e∈{0,1} satisfy the following inequalities and n=N(K,L,e).

3L²≤K², 3K²≤(3L+2)²; equivalently √3L≤K≤√3L+2/√3.

Necessity. Theorem 1 and the preceding lemma give an aligned complete lattice window. At θ=0 the wall calculation requires the nearer row to touch the wall for adjacent-row intervals to overlap. A single disc covers less than one unit and nonadjacent rows cannot connect, so both vertical walls contain sites. Thus 1=Kδ/2. Successive horizontal rows are √3/K apart. With L spacings between extreme rows and margins tᵦ,tₜ, one has tᵦ+tₜ=1−L√3/K.

Only the extreme row covers its corresponding horizontal wall, since the next row is at distance at least √3δ/2>h. Each row contains at least two sites spaced δ apart, and its worst horizontal distance is exactly δ/2. Consequently 0≤tᵦ,tₜ≤δ/(2√3), giving precisely the stated inequalities. Completeness of the window gives the alternating row counts in N. Conversely, choose symmetric margins m=(1−L√3/K)/2 and t=√3. Theorem 2 attains 2/√3. ∎

The margins need not be equal: all splits satisfying those bounds are allowed. For 10≤n≤40 the equality cardinalities are exactly 14,20,22,23,30. The two phases at K=4,L=2, together with Theorem 1, also settle n=7,8. The theorem does not completely classify n=5,6,9.

Equality cardinalities have natural density zero. For each L the K interval has length 2/√3<2, permitting at most two integers, each giving at most two cardinalities. Since n≥((L+1)²−1)/2, there are only O(√X) equality cardinalities up to X. In particular M₃₃,M₃₅>2/√3, but neither their exact optimum nor an explicit gap is obtained. Sparsity does not imply a uniform positive gap for other n and does not exclude Mₙ→2/√3.

8. Exact constructions, decimal certificates and competition settlement

Each row of the construction table gives an exact real-coordinate witness through Section 4 with t=√3. Theorem 1 supplies its matching lower bound. Figures are illustrations only; the proofs do not depend on pixels or floating-point sampling.

Finite-decimal coordinates cannot attain this bound. Equality in Theorem 1 contains a nondegenerate equilateral triangle. If its vertex coordinates were all rational, the determinant formula would give rational area, whereas the area is √3δ²/4 with δ² positive rational, a contradiction.

The P56 verifier computes M² exactly from nine-decimal coordinates and rounds M² upward at 10⁻¹⁵; the page separately displays an approximation to M. The internal target 4/3 and the public quantity 2/√3 must not be confused, and tolerances must not be widened to label an approximate record exactly optimal.

The site marks n=7,8,14,20,22,23,30 as “Proven optimum” and closes competition because their continuous problems are solved. Historical records, authorship and existing contribution points remain intact; the current certificates are not asserted optimal on the nine-decimal grid. Other cases remain open, particularly n=33,35: numerical agreement with a regular construction is not grounds for closure.

9. Conclusions and reproducibility

The results are a finite-cardinality lower bound, equality rigidity, classification of all equality cardinalities for n≥10, and exact optimization of a construction family with two integer and one continuous parameter. They organize several numerical records into a provable structural theory, but are not a formula for every Mₙ. Global optimization outside equality still requires new arguments; one cannot assume that all optima retain this row topology.

Enumeration of the classification needs only integer arithmetic; all coordinates and objective formulas are given above. Accompanying tests check cardinalities, integer conditions, the list of proved cases, and that decimalized witnesses pass the existing exact verifier without attaining 4/3. These tests check implementation consistency, not replace the analytic proofs.

Authorship: MinMax Arena. Claude and Codex assisted research discussion, derivation, exposition and code checking; this is a tooling disclosure, not an external peer-review claim. Corrections concerning proof gaps, overlooked prior work or stronger results are welcome in the P56 discussion board. Version: 2026-09-07, v1.

References

[1] Bishnu, Desai, Ghosh, Goswami and Paul — Uniformity of point samples in metric spaces using gap ratio (2015) ↗

[2] Teramoto, Asano, Katoh and Doerr — Inserting Points Uniformly at Every Instance (2006) ↗

[3] Bondarenko, Hardin and Saff — Mesh ratios for best-packing and limits of minimal energy configurations ↗