Source-linked AI summary
New Upper bounds on the Mondrian Art Problem
Thomas Garrison, Chris Seiler, Aliaksei Semchankau
TL;DR
The Mondrian Art Problem asks how to partition an n × n square into rectangles with distinct dimensions while minimizing the difference between the largest and smallest rectangle areas. The paper constructs such partitions with defect O(n^5/6), improving the previously conjectured O(n/log n) bound, and implements an algorithm achieving this asymptotic bound.
Problem
The problem seeks partitions of an n × n square into rectangles with distinct dimensions that minimize the difference between the largest and smallest rectangle areas.
Method
The paper uses strip tilings with carefully chosen distinct widths and heights so rectangle areas remain within a target interval.
Results
O(n^5/6) defect is achieved for sufficiently large n, with every rectangle having area Cn^7/6 ± O(n^5/6).
Takeaways & Limitations
The construction provides an implemented algorithm that achieves the paper’s theoretical O(n^5/6) upper bound.
Takeaways & Limitations
The paper leaves open whether better upper bounds exist and whether improved algorithms can reduce the defect further.
Abstract
from arXiv · showhide
We present a new upper bound on the defect of the Mondrian Art Problem. The Mondrian Art Problem asks for a partition of an $n \times n$ square with rectangles of distinct dimensions such that the difference (defect) between the largest and smallest rectangle areas is minimized. We prove that for any $n \times n$ square, there exists a partition with defect $O(n^{5/6})$, improving upon the previously conjectured $O (n/\log n)$ upper bound. We also implement an algorithm that provides empirical evidence supporting our theoretical bound.
1. Introduction
The Mondrian Art Problem seeks square partitions into rectangles with distinct dimensions while minimizing the area difference between the smallest and largest rectangles. This paper improves the conjectured upper bound through a polynomial construction and presents an example partition.
- The problem partitions an n × n square into rectangles with distinct dimensions, treating m × n and n × m as identical, while minimizing the smallest-to-largest area difference.
- Computations previously determined minimum defects for square sizes n = 3−57, while other work ruled out defect zero for sidelengths at most 1000.
- O(n/log n) was the computer-experimentation upper bound previously thought best for defects of n × n squares.
- The paper proves a polynomial improvement over that prior upper bound.
- The example 15×15 partition has defect 32 − 24 = 8.
2. Proof of the upper bound
The proof constructs a Mondrian partition by decomposing the square into strips and using subset-sum arguments to choose widths and heights. With widths Θ(n^1/2) and heights Θ(n^2/3), rectangle areas have defect O(n^5/6), yielding the stated upper bound for sufficiently large n.
- Strip construction: Choosing distinct heights Θ(n^2/3) that vary by Θ(n^1/3) gives rectangle areas Θ(n^7/6) and defect Θ(n^5/6).The heights and widths are separated in scale, ensuring dimensions remain distinct across strips.
- Result: For sufficiently large n, there exists a Mondrian partition with defect d ≤ 10n^5/6.The construction targets areas in [T − d, T + d], where d is proportional to n^5/6.
- Subset-sum argument: The subset-sum lemma represents every residue r up to s(s+1)/2 using a subset of {0, 1, . . . , s}.This removes the residue when expressing a target number relative to multiples of m.
- Subset-sum argument: Theorem 2.4 combines residue correction with symmetric choices of m ± b to represent the remaining multiple of m.The proof first selects elements summing to the residue and then constructs the remaining multiple from available terms.
3. Implementation
The implementation turns the strip-tiling construction into PartitionSquare, using RangeSubsetSum to select strip widths and producing defects of order O(n^5/6).
- Algorithm: PartitionSquare takes n as input and outputs a set of coordinate-specified rectangles forming a Mondrian partition.The algorithm represents each rectangle by opposite corners (x0, y0, x1, y1).
- RangeSubsetSum: RangeSubsetSum selects distinct widths from an interval centered on the median strip-width constant to match a target sum.Its inputs are positive integers m and target N, with widths drawn from [m−L, m+L] ∩ N under stated bounds on N and L.
- Parameter choice: The construction chooses a sufficiently large constant C so that the defect bound is valid for RangeSubsetSum.The constant is selected to satisfy the algorithm’s input requirements.
- Empirical evaluation: Every rectangle has area Cn^7/6 ± O(n^5/6), yielding defect O(n^5/6).The code is used to plot defects for square sizes from 1 × 10^9 to 2 × 10^10 in increments of 10^9.
4. Concluding remarks
The paper establishes an n^5/6 upper bound for large n and gives an algorithm achieving it, while identifying face-sharing and better constructions as open directions.
- Contributions: The paper proves an upper bound of n^5/6 for sufficiently large n and presents an algorithm that achieves it.The conclusion describes both the theoretical bound and its algorithmic realization.
- Open questions: Face-sharing often limits the tile sizes available in optimal Mondrian partitions by forcing rectangles to share dimensions.The discussion distinguishes adjacent rectangles from rectangles sharing one of the same dimensions.
- Open questions: The conclusion asks whether disallowing face-sharing can improve the upper bound and how families of such partitions can be constructed.It also asks whether more optimal algorithms could yield a better defect bound.
Appendix A.
The appendix justifies the subset-sum routines underlying the construction by maintaining an invariant relating selected values to their cardinalities.
- BasicSubsetSum: BasicSubsetSum is described as straightforwardly correct.The appendix presents it as the simpler routine used by RangeSubsetSum.
- RangeSubsetSum: RangeSubsetSum maintains the invariant that the sum of S− equals m multiplied by the size of S−.The proof also uses |S−| = k − |S+| to rewrite this sum as m(k − |S+|).
- RangeSubsetSum: RangeSubsetSum outputs a subset of [m−L, m+L] ∩ N whose elements sum to the target N.The algorithm takes m, L, and N as parameters.