ScienceAsia 42(2016): 150-157 |doi:
Optimal partitioning of a square: a numerical approach
Supanut Chaideea,b, Wacharin Wichiramalab,*
ABSTRACT: Optimal partitioning of a square is the search for the least-diameter way to partition a unit square into n pieces. The problem is here solved for some small n values. Although this problem has recently been approached by transforming the problem into a graphical enumeration, the algorithm had too large a computational cost for cases of n≥7. In this paper, the existence of solutions in a more general sense is established and the graphical transformation method is improved by generating dual graphs of the combinatorial patterns. In particular, combinatorial patterns were generated using the triangulation of planar graphs. Theorems to eliminate some unnecessary partitions are presented and numerical optimization by convex programming is used to find the minimum diameters. Our results confirm the earlier reported cases for n=9 and 10 and the predictions made for the case of n=11.
||Graduate School of Advanced Mathematical Sciences, Meiji University, 4-21-1 Nakano, Nakano-ku, Tokyo 164-8525, Japan
||Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, 254 Phayathai Road, Pathumwan, Bangkok 10330 Thailand
* Corresponding author, E-mail: firstname.lastname@example.org
Received 9 Mar 2015, Accepted 11 Apr 2016