Optimal partitions of the flat torus into parts of smaller diameter

D. S. Protasov, A. D. Tolmachev, Vsevolod A. VoronovDiscret. Optim 2025 · DOI · OpenReview

TL;DR

This paper investigates the problem of partitioning a 2D flat torus into a given number of pieces ($m$) such that the largest diameter among all pieces is minimized. The authors provide numerical estimates and exact results for small values of $m$, developing novel approaches involving SAT solvers, polygonal partitions, and hexagonal tilings.

What Problem Does This Paper Address?

The paper tackles a variation of the classic Borsuk problem, which asks if any bounded set in $n$-dimensional Euclidean space can be partitioned into $n+1$ subsets of strictly smaller diameter. Instead of focusing on the number of parts relative to dimension, this work asks: for a fixed number of parts ($m$), what is the smallest possible maximum diameter a part can have when partitioning a specific set – the 2D flat torus ($T^2$). This is a question about optimal partitioning for diameter minimization, which has seen less study than packing or covering problems. The flat torus is chosen because it lacks geometric constraints, making it a challenging and interesting case.

Methods

The authors employ a multi-pronged approach to estimate and, in some cases, determine the minimal maximal diameter, denoted as $d_m(T^2)$:

  • Strip Partitions: For small $m$, simple partitions using parallel "stripes" are used to derive upper bounds.
  • SAT Solvers: For larger $m$, the problem is framed as a graph coloring problem on a grid representing the torus. The graph coloring problem is then translated into a Boolean satisfiability (SAT) problem, which is solved using specialized solvers to find colorings (partitions) or prove that no coloring exists below a certain diameter threshold. This method yields both upper and lower bounds.
  • Polygonal Partitions: The paper explores partitions into polygons, specifically focusing on hexagonal tilings. This involves optimizing the shape and placement of hexagons to minimize their diameter.
  • Global Optimization: An optimization algorithm, adapted from previous work on planar sets, is used to find optimal partitions by minimizing the maximum diameter of the resulting polygons. This involves techniques like gradient descent and Voronoi diagrams.
  • Topological Reasoning: For $m=3$, an exact result is derived using elementary topological arguments involving colorings of lines on the torus.

Datasets

Not discussed in the paper. The paper focuses on theoretical and computational approaches to a geometric problem rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The flat torus is a challenging testbed: Its lack of boundaries and geometric constraints makes finding optimal partitions difficult, as optimal configurations can be shifted arbitrarily.
  • SAT solvers are powerful for geometric partitioning: Translating geometric partitioning problems into graph coloring and then SAT problems proves to be an effective method for obtaining bounds, especially for larger numbers of partitions.
  • Hexagonal tilings offer good candidates for optimal partitions: The paper shows that hexagonal tilings can lead to good upper bounds for $d_m(T^2)$, particularly for $m \ge 7$.
  • Exact results are rare and hard-won: While estimates are provided for many $m$, exact values are only proven for small $m$ (1, 2, 3), highlighting the difficulty of the problem.

Key Results

  • Exact values for small $m$:
    • $d_1(T^2) = d_2(T^2) = \frac{\sqrt{2}}{2} \approx 0.707107$
    • $d_3(T^2) = \frac{\sqrt{13}}{6} \approx 0.600925$
  • Upper and lower bounds for $4 \le m \le 7$: The paper provides tight bounds for these values, with the "gap" between upper and lower estimates being relatively small (e.g., 0.004 for $m=4$).
  • Numerical estimates for $1 \le m \le 25$: A table summarizes these estimates, showing a general decrease in $d_m(T^2)$ as $m$ increases.
  • Proof for $m=3$ using topological arguments: This demonstrates that for specific cases, rigorous proofs are achievable.

Limitations and Future Work

  • Exactness for $m \ge 4$: The paper acknowledges that for $m \ge 4$, they were unable to prove that the derived estimates are exact. This remains an open question.
  • Computational hardness: For larger $m$, the SAT solver approach becomes computationally intensive, as seen in Table 2.
  • Connectedness of parts: The paper notes that the regions in the partitions are not necessarily connected, which complicates reducing the problem to finite enumeration.
  • Future Work: The authors pose two open questions:
  • Are the estimates for $d_m(T^2)$ exact for $m=4, 5, 6$?
  • What is the shape of the set $M^*(\tau)$ that maximizes area for a given diameter $\tau$ on the torus?

Summary updated

Abstract

We consider the problem of partitioning a two-dimensional flat torus T2<math><msup is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup></math> into m<math><mi is="true">m</mi></math> sets in order to minimize the maximum diameter of a part. For m⩽25<math><mrow is="true"><mi is="true">m</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">⩽</mo><mn is="true">25</mn></mrow></math> we give numerical estimates for the maximum diameter dm(T2)<math><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">d</mi></mrow><mrow is="true"><mi is="true">m</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">T</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo is="true">)</mo></mrow></mrow></math> at which the partition exists. Several approaches are proposed to obtain such estimates. In particular, we use the search for mesh partitions via the SAT solver, the global optimization approach for polygonal partitions, and the optimization of periodic hexagonal tilings. For m=3<math><mrow is="true"><mi is="true">m</mi><mo linebreak="goodbreak" linebreakstyle="after" is="true">=</mo><mn is="true">3</mn></mrow></math>, the exact estimate is proved using elementary topological reasoning.
BibTeX
@article{protasov2025optimal,
  author = {D. S. Protasov and A. D. Tolmachev and Vsevolod A. Voronov},
  title = {{Optimal partitions of the flat torus into parts of smaller diameter}},
  journal = {Discret. Optim.},
  year = {2025},
  doi = {10.1016/j.disopt.2025.100890},
}

Loading related content...

Figure