Draft:Freedman's conjecture

Unsolved problem in mathematics

Given finitely many points in the unit square, one of which is the origin, can each point anchor the lower-left corner of an interior-disjoint rectangle packing covering at least half the square's area?

More unsolved problems in mathematics

Freedman's conjecture, also called the lower-left anchored rectangle packing problem (LLARP), is an open problem in computational geometry posed by Allen Freedman in 1969. It asks whether, for every finite set of points in the unit square that contains the origin, one can give each point a rectangle that has the point as its lower-left corner, with all rectangles interior-disjoint and together covering at least half the square.

An example input: the orange points are the point set, and each blue rectangle has an input point as its lower-left corner. The rectangles are interior-disjoint and avoid the remaining points, here covering 0.84 of the square. Whether every point set admits such a packing of area at least 1/2 is the conjecture.

The answer cannot be better than one half, since points spaced evenly along the ascending diagonal admit a maximum covered area of 1/2 + o(1) as their number grows. Freedman asked the question, and Bill Pulleyblank and Peter Winkler later conjectured that the answer is yes. The best known lower bound on the optimum is 0.39, due to Damerius, Kaaser, Kling and Schneider in 2021, who showed that the greedy TilePacking algorithm of Dumitrescu and Tóth covers at least 0.39 of the square on every input. The same analysis gives a point set on which the algorithm covers less than 0.433, which rules out this class of greedy algorithms as a route to the full conjecture.

Statement

Let U = [0, 1]² be the unit square and let P ⊆ U be a finite set of points with (0, 0) ∈ P. A lower-left anchored rectangle packing is a set of axis-aligned rectangles r_p ⊆ U, one for each point p ∈ P, such that:

• Each p is the lower-left corner of its rectangle r_p (the rectangle is anchored at p),
• the rectangles have pairwise disjoint interiors, and
• no rectangle contains any input point other than its own anchor in its interior.

The rectangles may be degenerate, that is, a point can be assigned an empty rectangle. The objective is to maximize the total covered area. The conjecture states that whenever (0, 0) ∈ P, the maximum is at least 1/2.

The problem can be formulated as a one-round game between two players, Alice and Bob: Alice picks the point set, and Bob then chooses the rectangles. The conjecture says Bob can always secure at least half the square.

History

Allen Freedman posed the problem in 1969, where it appeared as Unsolved Problem 11 in the proceedings of the Third Waterloo Conference on Combinatorics, edited by W. T. Tutte. Whether he expected a positive or a negative answer is not documented. The problem stayed dormant for decades and resurfaced at least twice, in IBM's Ponder This challenge of June 2004 and in Winkler's 2007 puzzle collection Mathematical Mind-Benders. Pulleyblank and Winkler conjectured the positive answer, and Dumitrescu and Tóth gave the problem its modern formulation together with the first constant coverage guarantee, in a preliminary version presented at SODA 2012 and in journal form in 2015.

Bounds

The diagonal example: with 10 equally spaced points on the ascending diagonal, the maximum coverable area is 1/2 + 1/(2·10) = 0.55, and in general 1/2 + 1/(2n). The value approaches 1/2 from above as n grows, so the conjectured bound cannot be improved. This construction is what makes 1/2 the natural target of the conjecture.

Dumitrescu and Tóth proved the first constant lower bound: their greedy algorithms always cover at least 0.09121 of the square, in a preliminary version presented at SODA 2012 and in journal form in 2015. The analysis partitions the square into staircase-shaped tiles, one per input point, and chooses a maximum-area rectangle within each tile. In a 2021 preprint, Hoeksma and Maat improved the lower bound to 0.1039 by studying greedy algorithms with a particular order of the input points. Later in 2021, Damerius, Kaaser, Kling and Schneider showed that TilePacking covers at least 0.39 of the square on every input, which is the best known lower bound on the optimum. They also constructed a point set on which the algorithm covers less than 0.433. No instance was known at the time on which the algorithm fell below 0.5, so this result ruled out the hope that a proof of the full conjecture could be obtained by analyzing this class of greedy algorithms alone. The gap between 0.39 and 1/2 therefore remains open, as does the computational complexity of the problem: it is not known whether computing a maximum-area packing is NP-hard.

Variants

Several variants relax or change the anchoring condition. If the rectangle of a point may be anchored at any of its four corners, the worst-case coverage lies between 7/12 − O(1/n) and 2/3, and it lies between 5/32 and 7/27 when the rectangles are restricted to squares. For squares anchored at the lower-left corner, a 1/3-approximation is known.

Antoniadis, Biermeier, Cristi, Damerius, Hoeksma, Kaaser, Kling and Nölke proved in 2019 that the center-anchored variant, where each rectangle must contain its input point at its center, is NP-hard, and they gave a polynomial-time approximation scheme for every anchoring in which the anchor lies in the interior of the rectangle. No hardness result is known for any variant with a single anchor on the boundary, which includes LLARP itself.

Under a resource-augmentation relaxation, where the anchor of every rectangle may move by at most ε from its point, there is an algorithm that covers as much area as an optimal unperturbed solution.

Applications

Map labeling is one application of anchored packing: rectangular text labels must be placed at fixed anchor positions inside a container without overlapping each other.

See also

• Packing problems
• List of unsolved problems in mathematics

References

Category:Unsolved problems in mathematics Category:Computational geometry Category:Discrete geometry Category:Packing problems