# Optimal partitioning of 2D meshes for stencil computations

Rob H. Bisseling, Bora Uçar

<figure><img src="image_1.png" /></figure>

## To cite this version:

Rob H. Bisseling, Bora Uçar. Optimal partitioning of 2D meshes for stencil computations. RR-9585, Inria Lyon. 2025. hal-05006840v2

HAL Id: hal-05006840

https://inria.hal.science/hal-05006840v2

Submitted on 22 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
informatics mathematics
Inria

Optimal partitioning of
2D meshes for stencil
computations

Rob H. Bisseling, Bora Uçar

RESEARCH
REPORT

Nº 9585

March 2025

Project-Team ROMA
<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /></figure>

Optimal partitioning of 2D meshes for stencil computations

Rob H. Bisseling*, Bora Uçar†‡

Project-Team ROMA

Research Report n° 9585 — version 2 — initial version March 2025 —
revised version September 2025 — 35 pages

**Abstract:** We study the partitioning of a regular rectangular mesh for the purpose of parallel 5-point stencil computations. In a well-defined formulation, the parts have an equal number of points, each part has a connected set of points, and the total communication volume is minimized. We present an optimal solution and a theoretical proof of optimality for the 16 × 16 mesh problem with 4 parts, as a representative of a larger class of regular mesh partitioning problems. The proof is based on a systematic derivation of isoperimetric inequalities that provide lower bounds on the number of neighbouring points of a part in different cases with up to 4 borders touched by the part.

The theoretical optimality result is confirmed by computations solving an Integer Linear Program (ILP) using Gurobi software, which took nine days using 32 concurrent threads. The ILP computation is made three orders of magnitude faster by adding heuristic constraints to the ILP as suggested by the theory. Finally, larger meshes of size up to 1024 × 1024 were tackled by a hybrid approach combining an initial combinatorial solution with a constrained ILP. The resulting communication volumes are presumably close to optimal. They are always better than the state-of-the-art hypergraph partitioning tools, with gains between 6.3% and 12.2% for the 1024 × 1024 mesh. Furthermore, the hybrid approach is faster than all except one partitioner; that partitioner is the one over which the proposed approach obtains the largest volume reduction for the 1024 × 1024 mesh.

**Key-words:** Mesh partitioning, Isoperimetric inequality, Parallel computing, Integer linear programming

RESEARCH CENTRE
Centre Inria de Lyon

Bâtiment CEI-2, Campus La Doua
56, Boulevard Niels Bohr - CS 52132
69603 Villeurbanne

<footnote>* Mathematical Institute, Utrecht University, Utrecht, The Netherlands</footnote>

<footnote>† CNRS and LIP (UMR5668 Université de Lyon - ENS de Lyon - UCBL - CNRS - Inria), 46 allée d'Italie, ENS Lyon, Lyon F-69364, France.</footnote>

<footnote>‡ Institute for Data Engineering and Science (IDEaS), Georgia Institute of Technology, Atlanta, GA, USA</footnote>
# Partitionnement optimal des maillages 2D pour les calculs de type stencil

**Résumé** : Nous étudions le partitionnement d'un maillage rectangulaire régulier dans le but d'effectuer des calculs parallèles avec un stencil à 5 points. Dans une formulation bien définie, les parties ont un nombre égal de points, chaque partie possède un ensemble connexe de points, et le volume total de communication est minimisé. Nous présentons une solution optimale ainsi qu'une preuve théorique d'optimalité pour le problème du maillage $16 \times 16$ avec 4 parties, en tant que représentant d'une classe plus large de problèmes de partitionnement de maillages réguliers. La preuve repose sur une dérivation systématique d'inégalités isopérimétriques fournissant des bornes inférieures sur le nombre de points voisins d'une partie dans différents cas, avec jusqu'à 4 frontières touchées par la partie.

Le résultat théorique d'optimalité est confirmé par des calculs résolvant un programme linéaire en nombres entiers (ILP) à l'aide du logiciel Gurobi, ce qui a pris neuf jours avec 32 threads en parallèle. Le calcul de l'ILP est accéléré de trois ordres de grandeur en ajoutant des contraintes heuristiques à l'ILP, comme suggéré par la théorie. Enfin, des maillages plus grands, allant jusqu'à $1024 \times 1024$, ont été traités par une approche hybride combinant une solution combinatoire initiale avec un ILP. Les volumes de communication obtenus sont vraisemblablement proches de l'optimal. Ils sont toujours meilleurs que ceux des outils de partitionnement d'hypergraphes les plus avancés, avec des gains compris entre 6.3% et 12.2% pour le maillage $1024 \times 1024$. De plus, l'approche hybride est plus rapide que tous les partitionneurs sauf un; ce dernier est précisément celui sur lequel l'approche proposée obtient la plus grande réduction de volume pour le maillage $1024 \times 1024$.

**Mots-clés** : Partitionnement de maillage, Inégalité isopérimétrique, Calcul parallèle, Programmation linéaire en nombres entiers
# Contents

<table><tr><td>1 Introduction</td><td>4</td></tr><tr><td>2 Preliminaries and related work</td><td>6</td></tr><tr><td>3 Communication lower bounds for separate parts</td><td>7</td></tr><tr><td>3.1 Case T = 2</td><td>7</td></tr><tr><td>3.2 Case T = 1</td><td>10</td></tr><tr><td>3.3 Case T = 0</td><td>14</td></tr><tr><td>3.4 Case T = 3</td><td>19</td></tr><tr><td>3.5 Case T = 4</td><td>19</td></tr><tr><td>3.5.1 Dropping operation</td><td>19</td></tr><tr><td>3.5.2 Case T = 4 with dense rows or columns</td><td>21</td></tr><tr><td>3.5.3 Case T = 4 without dense rows or columns</td><td>24</td></tr><tr><td>4 Using the theoretical findings</td><td>25</td></tr><tr><td>4.1 Optimal partitioning of a square 16 × 16 mesh into 4 parts</td><td>25</td></tr><tr><td>4.1.1 Individual cases</td><td>25</td></tr><tr><td>4.1.2 Combining the individual cases</td><td>26</td></tr><tr><td>4.2 Developing heuristics</td><td>28</td></tr><tr><td>4.2.1 Purely combinatorial approach</td><td>28</td></tr><tr><td>4.2.2 Heuristics for ILP solvers</td><td>29</td></tr><tr><td>4.2.3 Hybrid heuristic</td><td>30</td></tr><tr><td>5 Computational results</td><td>30</td></tr><tr><td>6 Concluding remarks</td><td>32</td></tr></table>
<figure><img src="image_5.png" /><figcaption>Figure 1: Two-dimensional $I \times J$ mesh with $I = 6$ and $J = 4$.</figcaption></figure>

# 1 Introduction

In numerically solving partial differential equations with the finite difference method, a physical domain is discretised and a computational domain of a set of discrete points is obtained. A suitable pattern, called *stencil*, around each point is defined, where the computational scheme updates a value at each point using the other points in this pattern. We are interested in two dimensional (2D) domains and discretisation using the five-point stencil, where two points $(i_1, j_1)$ and $(i_2, j_2)$ of the resulting mesh are neighbours iff $|i_1 - i_2| + |j_1 - j_2| = 1$. In these $I \times J$ meshes, a point itself is also in the stencil, so that the required computations proceed by updating the value of each point using its current value and the current values of all its neighbours.

A 2D mesh of size $I \times J$ has mesh points $(i, j)$, where each coordinate is numbered from 0, so $0 \le i < I$ and $0 \le j < J$. All coordinates $i$ and $j$ in this article will be integers. We also assume that $I, J \ge 2$. In visualisations, we identify each mesh point $(i, j)$ with a small circle, where the point is at the centre. Point $(0, 0)$ is at the bottom left and point $(I - 1, J - 1)$ at the top right, see Figure 1. *Column i* consists of all mesh points with first coordinate $i$, and *row j* consists of all mesh points with second coordinate $j$. The *neighbours* of a point $(i, j)$ are the points $(i - 1, j)$, $(i + 1, j)$, $(i, j - 1)$, $(i, j + 1)$ whenever they exist. Each interior point of the mesh has four neighbours; each corner point has only two neighbours; and the remaining border points possess three neighbours. In the figures, a point is connected with an edge to each of its neighbors.

A mesh can be partitioned for the purpose of a parallel 5-point stencil operation, where each processor of a parallel computer obtains a part of the mesh points. A *part* of the partitioning is a *connected* subset $V$ of the points, where the connections are provided by the edges of the mesh. In a $K$-way partitioning, there are $K$ nonempty parts, numbered $k = 0, 1, \dots, K - 1$. A part *touches the left border* of the mesh if it includes a point $(0, j)$. It touches the right border if it includes a point $(I - 1, j)$, and similar for the bottom and top borders. We denote the number of touched borders by $T = T(V)$, with $0 \le T \le 4$. The set $V$ of Figure 2 is a part since it is connected, and it touches the bottom and right borders, so $T(V) = 2$.

The requirement that a part should be connected is imposed for several reasons: first, many applications require the outcome of partitioning a connected problem to be connected parts; second, merging several connected components into a single connected component usually reduces the number of neighbours; third, it helps obtaining theoretical results on the number of neighbours.

The total *communication cost* $C$ of a parallel 5-point stencil operation is the communication volume incurred by transferring all the needed data to the processors responsible for the respective
parts in the partitioning. We can calculate *C* by summing the number of data words received for all the parts. We can compute the number *R(V)* of received data words of a part *V* simply by counting its neighbours. Here, the set *N(V)* of *neighbours of a part V* is defined as the set of all neighbours of vertices in *V*, except for those neighbours that are themselves member of *V*. Thus, *R(V) = |N(V)|*. We could calculate *C* also by summing the number of data words sent, but the number of sends for a part also depends on the configuration of its neighbours.

We are interested in a particular problem in which a square mesh is to be partitioned into four parts having an equal number of points each, while minimising the total communication cost. We are not aware of any polynomial time algorithm for this particular problem, whose general version is known as the NP-complete hypergraph partitioning problem. We develop analytical tools to verify that a 4-way partition of the 16 × 16 mesh with communication cost *C* = 57, claimed to be optimal in earlier work [2], is in fact optimal. Our analytical tools are derived and proved for the general case and are thus useful in considering more general cases. We make use of them in developing a set of heuristic decisions for an integer linear programming-based solution, and for developing a practical heuristic which obtains the best known bound for *C* for a number of partitioning problems.

Many physical applications require much more elaborate meshing techniques than the one we
consider. Furthermore, balancing the number of mesh points per processor does not necessarily
lead to perfect computational load balance, as the interior points, border points, and the corner
points have different computational cost with the 5-point stencil. Nonetheless, the theoretical
results developed here will shed light on practical approaches. For example, we can check the
performance of sparse matrix and hypergraph partitioners on a regular mesh problem. For
this, the mesh partitioning problem can be translated to an equivalent sparse matrix problem,
with every matrix row representing a mesh point and every off-diagonal nonzero in the matrix
representing a connection with one of the four neighbours. This is done for example in [5, Section
4.9], where the Mondriaan sparse matrix partitioner is used to partition a 12 × 12 mesh into 8
nearly equal-sized subsets, showing a preference for connected parts and for stepwise boundaries
between parts. Furthermore, the special case we treat is the basis for a fast Breadth-First-Search
(BFS) partitioning algorithm [13] for the general rectangular case.

The ultimate goal for this line of work is to find an optimal balanced *K*-way partitioning of
the *I* × *J* mesh, i.e., with every part having a connected set of *IJ/K* mesh points, and with the
minimum total communication cost *C*. Previous approaches [13, 18] with a similar goal start
with a 4-way partitioning of a smaller square mesh and extend that partitioning to a general
*I* × *J* mesh and the desired number of parts. These approaches demonstrate significant gains
with respect to the standard partitioning tools. The contributions of the current paper explain
the success of the previous work for the 4-way partitioning case.

This paper also develops theory that gives lower bounds for the communication volume of
a part in an *I* × *J* mesh, exhaustively covering the separate cases of the number of borders
*T*(V) ≤ 4 that a part can touch. Here, we build on techniques by Wang and Wang [21] who
obtained optimal multidimensional shapes for a single part; in two dimensions this solves the
cases *T*(V) = 0 and *T*(V) = 2. Bollobás and Leader [7] provide a different proof for the case
*T*(V) = 2 based on compressing the set *V* while reducing the cost *R*(V). We will build on this
for the case *T*(V) = 4. Our inequalities in all cases, including *T*(V) = 0, 2, 4 are proven with
detailed arguments. Such problems concerning the minimal boundary size for a single part are
known as *discrete isoperimetric inequality* problems. Earlier studies in this area consider a single
part and its complement in an infinite mesh, but not the overall partitioning problem into *K*
parts. To the best of our knowledge, the derived isoperimetric inequalities for the cases of a part
touching one, three, and four borders are novel. Furthermore, to the best of our knowledge, no
previous work has combined individual case results to demonstrate an optimal partition. We
<figure><img src="image_6.png" /><figcaption>Figure 2: Rectangular hull $H(V)$ of a connected set (part) $V$ of 12 mesh points. The hull and the mesh points of the set are shown in red. The height of the hull is $h = 3$ and its width is $w = 5$. The number of receives is $R(V) = 6$ and the number of touched borders is $T(V) = 2$.</figcaption></figure>

achieve this for the 4-way partitioning of the 16 × 16 mesh. More recent work along these lines investigates the optimum shape of a part in meshes of various underlying geometry (including the meshes addressed here), methods for counting those shapes, and the properties of optimum shapes in different sizes [3, 4, 19].

## 2 Preliminaries and related work

The rectangular hull $H = H(V)$ of a set of mesh points $V$ is the smallest rectangle that encloses all the points of $V$, see Figure 2. The height $h$ of the hull is the number of rows of the mesh that intersect $V$ and the width $w$ is the number of columns that intersect $V$. Note that the height is not the distance between top and bottom row of the hull, but the distance plus 1; similar for the width.

We say that a column $i$ is dense for $V$ if all its points are in $V$, and similar for a row $j$. We denote the column index of the leftmost point from $V$ in row $j$ of the mesh by $l(j) = \text{argmin}\{i : (i, j) \in V\}$, and the column index of the rightmost point in row $j$ by $r(j) = \text{argmax}\{i : (i, j) \in V\}$. Similarly, we define $b(i)$ and $t(i)$ for the bottom and top points of column $i$.

An example of a part $V$ with $T(V) = 0$ and with an optimal shape is the ball of integer radius $r \ge 0$ with centre $(c_0, c_1)$, also called digital diamond, defined as

$$B_r(c_0, c_1) = \{(i, j) : |i - c_0| + |j - c_1| \le r\}. \quad (1)$$

The ball of radius $r$ contains $2r^2 + 2r + 1$ mesh points and it has $4r + 4$ neighbours. Its hull has width $w = 2r + 1$ and height $h = 2r + 1$. Figure 3 shows a ball of radius 3. The optimality is in terms of a minimal number of receives for a given number of mesh points in the ball. Optimality of the ball $B_r$ for $2r^2 + 2r + 1$ mesh points has been proven by Wang and Wang [21], and also for balls with other numbers of mesh points that have part of their boundary empty.

Bisseling and McColl [6] showed how to fit 25 digital diamonds of radius 3 together by a periodic tiling to partition a 25 × 25 mesh with the aim of minimising the communication cost. In their work, the mesh borders create partial diamonds which can be combined based on wrapping around at mesh borders, yielding complete, albeit disconnected diamonds. The basic tile is made more flexible in [5, Section 4.9] by shaving off two boundaries. This enables cutting up a square mesh into small square blocks, and then placing a tile at every corner and centre of the blocks.

Two previous studies [13, 18] propose heuristic approaches for the partitioning problem addressed in this paper. These two works are empirical; they propose heuristics and show improved partitioning results with respect to general solvers. They do not delve into the theoretical properties of the proposed heuristics. This paper improves the previous studies by showing optimality of certain decisions inside those previous works. A slight modification of one of the heuristics [13],
<figure><img src="image_7.png" /><figcaption>Figure 3: Ball $V = B_r(c)$ of radius $r = 3$ and centre $c$, with $|V| = 25$, $R(V) = 16$, $T(V) = 0$. The points of the ball are shown as red closed disks. The hull $H(V)$ is shown as a red rectangle.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 4: A part $V$ of 12 mesh points touching the bottom and top borders. The points of $V$ are shown as red closed disks. The $R(V) = 12$ neighbours are shown as blue circles. The hull $H(V)$ is shown as a red rectangle. The height of the hull is $h = 6$ and the width is $w = 2$.</figcaption></figure>

mentioned elsewhere [2], obtains an optimal solution for the 16 × 16 mesh. We improve this method with heuristics that we derive from our theoretical analysis and show the best results known so far for a number of partitioning problems.

There are other works for general mesh partitioning, see for example [1, 9, 11, 15, 16, 20]. These methods are developed for irregular meshes, in which the underlying discretisation is much more complex than what this paper addresses. For this reason, we do not survey this line of work further.

# 3 Communication lower bounds for separate parts

We derive lower bounds on the number of receives for separate parts, irrespective of the configuration of their neighbouring parts. We will do this by distinguishing the possible cases from $T = 0$ to $T = 4$, but in a different order, starting with the easiest case $T = 2$.

## 3.1 Case $T = 2$

The case of two touched borders is straightforward if these borders are not adjacent, see Figure 4.

**Lemma 3.1.** Let $V$ be a part with $T(V) = 2$ that touches two nonadjacent borders. If these
borders are the bottom and top borders, then $R(V) \ge 2J$. If they are the left and right borders, then $R(V) \ge 2I$.

*Proof.* Assume that the touched borders are at the bottom and the top. Since $V$ does not touch the left border, there exists a point $(i, j) \notin V$ to the left of $V$ in every row $j$, $0 \le j < J$, as $V$ is connected so that there exists a path from bottom to top in $V$. Hence, $V$ has at least $J$ left neighbours. Similarly, $V$ has at least $J$ right neighbours, so $R(V) \ge 2J$. The case for $V$ touching the left and right borders is proven in a similar way. □

The optimal number of neighbours for this case is $R(V) = 2J$, since we can attain the lower bound by assigning the complete columns $1, \dots, \lfloor n/J \rfloor$ of the mesh to part $V$, where $n = |V|$, as well as the bottom $n$ mod $J$ points of the next column.

Let us now consider the case that $V$ touches two adjacent borders. The following lemma can be used to derive a lower bound on the number of neighbours for parts that contain a point at in the interior of the mesh and touch two adjacent borders. It will also be used in the proof of Lemma 3.3 which gives the optimal lower bound for $T = 2$.

**Lemma 3.2.** Let $V$ be a part with $T(V) = 2$ that touches the bottom and left borders. For any given point $(i, j) \in V$,

$$R(V) \ge i + j + 2.$$

*Proof.* For a point $(i, j) \in V$, let $N_r = \{(r(j') + 1, j') : 0 \le j' \le j\}$ be the set of neighbours to the right of the rightmost points in rows $0$ to $j$. These neighbours exist since $V$ is connected; there is a path from $(i, j)$ to the bottom border and $V$ does not touch the right border. There are $j+1$ points in $N_r$. Similarly, let $N_t = \{(i', t(i') + 1) : 0 \le i' \le i\}$ be the set of neighbours above the top points in columns $0$ to $i$; there are $i+1$ points in $N_t$. The part $V$ should receive the values from all points in $N_r \cup N_t$. We will show that $N_r \cap N_t = \emptyset$, which immediately yields that $R(V) \ge |N_r \cup N_t| = |N_r| + |N_t| = i + j + 2$.

Assume for the sake of contradiction that we have a neighbour $(a_1, a_2) \in N_r \cap N_t$ as shown in Figure 5. We have $a_1 \le i$ and $a_2 \le j$, because $N_t$ has the restriction $a_1 \le i$ and $N_r$ has $a_2 \le j$. Furthermore, $(i', a_2) \notin V$ for all $i' \ge a_1$ because $(a_1, a_2)$ is the neighbour to the right of the rightmost point of $V$ in row $a_2$, and similarly $(a_1, j') \notin V$ for all $j' \ge a_2$. Therefore, the connectivity of $V$ implies that $(i', j') \notin V$ for all $i' \ge a_1$ and $j' \ge a_2$. This is a contradiction because $(i, j) \in V$ and $i \ge a_1$ and $j \ge a_2$.

As a result, we have proven that $N_r \cap N_t = \emptyset$. □

**Lemma 3.2** gives a lower bound and not an equality for several reasons. First, it concerns any point $(i, j) \in V$, and there may exist points $(i', j') \in V$ with $i' + j' > i + j$. Second, if not all rows touch the left border, or if not all columns touch the bottom border, there may be additional neighbours to the left or below, yielding additional neighbours. Finally, there may be internal holes in a row of $V$, so that there exist neighbours that are not the leftmost nor the rightmost neighbours in a row of $V$, and similar for columns.

Define wavefront $W_k = \{(i, j) : i, j \ge 0 \land i + j = k\}$ for $k \ge 0$, so that $|W_k| = k + 1$. Define the function denoting the total number of points in wavefronts $W_0, W_1, \dots, W_k$ by

$$\phi_2(k) = \sum_{r=0}^{k} (r+1) = \frac{(k+1)(k+2)}{2}. \qquad (2)$$

We call a set of points $W \subseteq W_k$ from a wavefront $W_k$ contiguous if there are $i_0, i_1$ such that $W = \{(i, k - i) : i_0 \le i \le i_1\}$.

The following Lemma was stated as Lemma 4.1 by Wang and Wang [21].
<figure><img src="image_9.png" /><figcaption>Figure 5: A part V of 24 mesh points touching the left and bottom borders. The mesh points of V are shown as red closed disks. Point a = (a₁, a₂) is a neighbour of the top point of V in its column and also a neighbour of the rightmost point in its row. This implies that all points shown in blue cannot be in V, and as a consequence of the connectivity of V, the whole top-right rectangle shown in blue cannot contain points of V.</figcaption></figure>

**Lemma 3.3.** Let V be a part with $n = |V|$ mesh points and $T(V) = 2$ that touches the bottom and left borders. Let k be such that $\phi_2(k) < n \le \phi_2(k+1)$. Then

$$R(V) \ge k + 3.$$

The lower bound $R(V) = k + 3$ is attained by a set of mesh points S consisting of the $\phi_2(k)$ points of $\cup_{r=0}^k W_r$ and $n - \phi_2(k)$ contiguous points from $W_{k+1}$.

*Proof.* The proof is a direct translation of the proof of [21, Lemma 4.1] to the two-dimensional case where a set of the form of S is called a 'standard sphere'.

Assume that V, S, and k are as given. Take a point $(i, j) \in V$ with $i + j \ge k + 1$. If such a point does not exist, then $V \subseteq \cup_{r=0}^k W_r$, so $|V| = n \le \phi_2(k)$, which is a contradiction. Now apply Lemma 3.2, which gives $R(V) \ge i + j + 2 \ge k + 1 + 2 = k + 3$.

For $V = S$, we have $R(V) = k + 3$, as follows. First, there are $s = n - \phi_2(k)$ points in $W_{k+1}$, namely $(i, k + 1 - i)$, $i_0 \le i < i_0 + s$, that have a total of $s + 1$ neighbours in $W_{k+2}$, namely the set $(i, k + 2 - i)$, $i_0 \le i \le i_0 + s$. Second, the remaining $k + 2 - s$ points in $W_{k+1}$ are neighbours of points in $W_k$. The number of elements of these two disjoint set of neighbours is $(s + 1) + (k + 2 - s) = k + 3$, hence reaching the lower bound on $R(V)$. $\square$

This means that sets of the form S are optimal for $T(V) = 2$. Figure 6 gives an example set $V = S$ with $n = 25$, where $k = 5$ and $s = 4$.

The simplicial ordering [7] on the points of an $I \times J$ mesh is defined by $(i, j) < (i', j')$ iff $i + j < i' + j'$ or $i + j = i' + j'$ and $i > i'$. The points of the mesh in increasing simplicial order are thus $(0,0)$, $(1,0)$, $(0,1)$, $(2,0)$, $(1,1)$, $(0,2)$, ..., $(I - 2, J - 1)$, $(I - 1, J - 1)$. Bollobás and Leader prove that the first $n$ points in this order form a set $S$ that attains the lower bound of Lemma 3.3 for an infinite grid (taking $I = J = \infty$ in our notation), a result earlier obtained by Wang and Wang [21]. This result corresponds to choosing $i_0 = k + 2 - s$ in the proof of the lemma. Furthermore, they also prove that taking the first $n$ points in the simplicial order within an $I \times I$ mesh has minimal boundary size, even if more than two borders are touched. The resulting subset is connected, so it is a part. Note that this problem is not the same as finding a part V with $n$ points and minimal boundary size that satisfies the constraint of touching three borders, or four borders.

We can increase the lower bound of Lemma 3.3, if part V does not contain a corner point, as stated in the following lemma.
<figure><img src="image_10.png" /><figcaption>Figure 6: An optimal part V of 25 mesh points that touches two adjacent borders. The mesh points of V are shown as red closed disks. Wavefronts $W_0, \dots, W_5$ are completely filled by V; $W_6$ has 4 additional points from V. The nodes on the dashed line represent wavefront $W_5$. The $R(V) = 8$ neighbours are shown as blue circles.</figcaption></figure>

**Lemma 3.4.** Let V be a part with $T(V) = 2$ that touches the left and bottom border, and let $V' \neq V$ be another part with $(0,0) \in V'$. Let $n = |V|$ and $n' = |V'|$, and let $k$ be such that $\phi_2(k) < n + n' \le \phi_2(k+1)$. Then

$$R(V) \ge k + 3 + \lfloor \sqrt{n'} \rfloor.$$

*Proof.* Let P be a path in V from the left border to the bottom border. Let $V_0$ be the set of vertices enclosed by the path on the side of the corner point $(0,0)$. Note that $V' \subseteq V_0$ and that $V \cup V_0$ is connected. We can now apply Lemma 3.3 to the connected vertex set $V \cup V_0$, and note that the $k+3$ neighbours thus obtained are above or to the right of the path P, cf. the proof of Lemma 3.2. On the other hand, there are at least $\lfloor \sqrt{n'} \rfloor$ neighbours of V below or to the left of path P, because the corner $(0,0) \in V'$ is there, and $V'$ is connected, see Figure 7. This means that the hull of $V'$ has one side of size at least $\lfloor \sqrt{n'} \rfloor$; if this is for instance the top side then V must receive at least $\lfloor \sqrt{n'} \rfloor$ values from below (originating in $V_0 \setminus V$, not necessarily in $V'$). $\square$

## 3.2 Case $T = 1$

First, we state two straightforward lemmas that are useful for handling cases with $T = 1$.

**Lemma 3.5.** Let part V have a hull of height h and width w, and $T(V) = 1$. Assume that a side of the hull of length w coincides with the touched border. Then

$$R(V) \ge \max\{2h + 1, w + 2\}.$$

*Proof.* Assume without loss of generality (wlog) that the touched border is the bottom border. Since V does not touch the left border, there exists a point $(i,j) \notin V$ to the left of the hull in every row j, $0 \le j < h$, so V has at least h left neighbours (they may be inside or outside the hull). Similarly, V has at least h right neighbours. Since the hull does not touch the top border, there exists at least one neighbour above V. This gives a total of at least $2h+1$ distinct neighbours, namely $2h$ in rows 0 up to $h-1$ and 1 above the hull in row h.
<figure><img src="image_11.png" /><figcaption>Figure 7: A part V of 19 mesh points that touches two adjacent borders but does not contain its corner point. The mesh points of V are shown as red closed disks. The corner and 5 other points shown as blue disks are contained in a different part V'. The eight neighbours above and to the right of V are shown as blue circles; three other neighbours belong to V'. The total number of neighbours of V is $R(V) = 11$. The hull of V' is shown as a blue rectangle with width 3 and height 3. The lower bound given by Lemma 3.4 with values $n + n' = 25$ and $k = 5$ states that $R(V) \ge 11$.</figcaption></figure>

Since V does not touch the top border, there are at least w neighbours above V. Furthermore, since V does not touch the left and right borders, there will be at least one additional distinct neighbour to the left and one to the right in row 0 of V. This gives a total of at least w + 2 distinct neighbours. Taking the maximum of the two neighbour counts gives the desired lower bound on $R(V)$. $\square$

**Lemma 3.6.** Let V be a part with $T(V) = 1$ that touches the bottom border. Let $(i, j) \in V$. Then

$$R(V) \ge 2j + 3.$$

*Proof.* Let $N_1 = \{(l(j') - 1, j') : 0 \le j' \le j\}$ be the set of neighbours to the left of the leftmost points of V in rows 0 to j. These neighbours exist since there is a path from $(i, j)$ to the bottom border and V does not touch the left border. Similarly, let $N_r = \{(r(j') + 1, j') : 0 \le j' \le j\}$ be the set of neighbours to the right of the rightmost points in rows 0 to j. These neighbours also exist. Furthermore, the sets $N_1$ and $N_r$ are disjoint, because $l(j') - 1 \le r(j') - 1 < r(j') + 1$ for each $j'$. Another neighbour is $(i, t(i) + 1)$, which is disjoint from the $2j + 2$ other neighbours, because $t(i) \ge j$, so that $t(i) + 1 > j$. $\square$

We now aim to obtain a sharp lower bound on R for the case $T = 1$. Our approach for this case was inspired by the proof for the case $T = 2$ by Wang and Wang [21, Lemma 4.1], see also our Lemma 3.3.

Define *pyramid* $P_k$ for $k \ge 0$ by

$$P_k = \{(i, j) : j \ge 0 \land j \le i \le k - j\}.$$

Define the function denoting the number of points of $P_k$ by

$$\phi_1(k) = (k+1) + (k-1) + (k-3) + \dots = \begin{cases} \frac{(k/2+1)^2}{2} & \text{if } k \text{ is even,} \\ \frac{(k+1)(k+3)}{4} & \text{if } k \text{ is odd.} \end{cases} \quad (3)$$

Figure 8 shows a pyramid for $k = 8$. A pyramid can undergo translations by adding $(a_i, a_j)$ to each point. We use $(a, 0) + P_k$ to denote the pyramid $P_k$ shifted by a points along the first coordinate direction.
<figure><img src="image_12.png" /><figcaption>Figure 8: Pyramid $V = P_8$ with 25 mesh points. The mesh points of $V$ are shown as red closed disks. The dashed lines show the defining boundaries of the pyramid.</figcaption></figure>

**Lemma 3.7.** Let $V$ be a part with $n = |V|$ mesh points and $T(V) = 1$ that touches the bottom border. Let $k$ be such that $\phi_1(k) < n \le \phi_1(k+1)$. Then

$$R(V) \ge k + 4.$$

The lower bound $R(V) = k+4$ is attained by a set of mesh points $S$ consisting of the $\phi_1(k)$ points of the shifted pyramid $(a,0)+P_k$ and the $r = n-\phi_1(k)$ points from $\{(a+k+1-j, j) : 0 \le j < r\}$, provided $a \ge 1$ so that $S$ does not touch the left border and also provided that the $I \times J$ mesh is large enough so that $S$ does not touch the right and top borders.

*Proof.* Let $V$ be a part with $T(V) = 1$ that touches the bottom border. Define

$$ 
\begin{align} 
a &= \min \{i-j : (i,j) \in V\}, \\ 
b &= \max \{i+j : (i,j) \in V\}. 
\end{align} 
\tag{4} $$

Note that $a \le b$, because $i-j \le i+j$ for every point $(i,j) \in V$. Furthermore,

$$V \subseteq (a, 0) + P_{b-a}, \tag{5}$$

i.e., $V$ is contained within the pyramid $P_{b-a}$ shifted by $a$ points to the right. This can be seen by rewriting the set $(a,0) + P_{b-a}$ as

$$ 
\begin{align*} 
(a,0) + P_{b-a} &= \{(i+a, j) : j \ge 0 \land j \le i \land i \le b-a-j\} \\ 
&= \{(i+a, j) : j \ge 0 \land j + a \le i + a \le b-j\} \\ 
&= \{(i', j) : j \ge 0 \land a \le i' - j \land i' + j \le b\}. 
\end{align*} 
$$

For general $V$, the shift parameter $a$ can be negative, in which case the pyramid extends beyond the mesh.

As a consequence, $|V| \le \phi_1(b-a)$. Because it also holds that $|V| > \phi_1(k)$ and because $\phi_1(k)$ is a monotonically increasing function, we have

$$b-a \ge k+1.$$

Take a point $(a_1, a_2) \in V$ with $a_1 - a_2 = a$ and a point $(b_1, b_2) \in V$ with $b_1 + b_2 = b$, as shown in Figure 9; note that there may be more than one possible point in each case. As $a_1 + a_2 \le b$ by the definition of $b$, we obtain $a_1 \le (a+b)/2$ by substituting $a_2 = a_1 - a$. Similarly, $b_1 \ge (a+b)/2$ follows by noting that $b_1 - b_2 \ge a$ and substituting $b_2 = b - b_1$. Therefore, it also holds that $a_1 \le b_1$.
<figure><img src="image_13.png" /></figure>

Figure 9: A part V of 23 mesh points that touches one border. The mesh points of V are shown as red closed disks. The dashed lines represent mesh points with $i-j = a = 1$ and $i+j = b = 10$, respectively. A point **a** = ($a_1, a_2$) is chosen on line $i-j = a$, and a point **b** = ($b_1, b_2$) on line $i+j = b$. The $R(V) = 13$ neighbours of V are shown as blue circles. Using the points **a** and **b**, the neighbour sets $N_l$, $N_t$, and $N_r$ can be formed, which are shown by the points marked ‘l’, ‘t’, ‘r’, with 3, 7, and 2 points, respectively, giving a lower bound $R(V) \ge 12$. The blue point (4,4) is a neighbour, but it is not labeled because it does not belong to one of the three neighbour sets.

There are at least $a_2+1$ neighbours to the left of V, because V touches the bottom border but not the left border. These are marked ‘l’ in Figure 9. Similarly, there are at least $b_2+1$ neighbours to the right of V. Furthermore, there are at least $b_1-a_1+1$ neighbours above V in columns $a_1$ up to $b_1$, because there is a path in V from ($a_1, a_2$) to ($b_1, b_2$) and V does not touch the top border. The total number of neighbours is thus $(a_2+1)+(b_2+1)+(b_1-a_1+1) = b-a+3 \ge k+4$, where we used the inequality $b-a \ge k+1$ from above. Our neighbour count holds provided the three sets of neighbours are mutually disjoint, which we will show next.

Let $N_l = \{(l(j) - 1, j) : 0 \le j \le a_2\}$ be the set of neighbours of the leftmost points of V in rows 0 to $a_2$. Let $N_r = \{(r(j) + 1, j) : 0 \le j \le b_2\}$ be the set of neighbours of the rightmost points of V in rows 0 to $b_2$. Let $N_t = \{(i, t(i) + 1) : a_1 \le i \le b_1\}$ be the set of neighbours of the topmost points of V in columns $a_1$ to $b_1$.

It must hold that $N_l \cap N_r = \emptyset$. Otherwise, for $(i,j) \in N_l \cap N_r$, we must have that $j \le \min\{a_2, b_2\}$ by construction, and furthermore $i = l(j) - 1 = r(j) + 1$. This implies that $l(j) > r(j)$, which is a contradiction.

We will now show that $N_r \cap N_t = \emptyset$. The proof that $N_l \cap N_t = \emptyset$ is similar. If $(i,j) \in N_r \cap N_t$, we have that $(i,j) \notin V$, and that $i \le b_1$ and $j \le b_2$. Furthermore $(i',j') \notin V$ for all $i' \ge i$ and $(i,j') \notin V$ for all $j' \ge j$, which by connectivity of V implies that the whole enclosed rectangle cannot be in V, i.e., $(i',j') \notin V$ for all $i' \ge i$ and $j' \ge j$. Since $(b_1,b_2) \in V$, this implies $b_1 < i$ or $b_2 < j$, which is a contradiction. Thus the intersection of $N_r$ and $N_t$ is empty and the three neighbour sets are disjoint.

For the set S, which is contained in the pyramid $(a,0)+P_{k+1}$, we have $a \ge 1$ so that V touches only the bottom border. Furthermore, we have $R(V) = k+4$, because there is one neighbour in each column from $i=a$ to $i=a+k+1$, namely the neighbour $(i,t(i)+1)$ directly above V, and furthermore the two neighbours $(a-1,0)$ and $(a+k+2,0)$.

<figure><img src="image_14.png" /></figure>

Figure 10 gives an example set $V = S$ which fills the shifted pyramid $(1,0)+P_8$ and adds three points from $(1,0)+P_9$. This corresponds to the case $n=28$, where $k=8$ and the lower bound $R(V) = k+4$ is attained.
<figure><img src="image_15.png" /><figcaption>Figure 10: An optimal part V of 28 mesh points that touches one border. The mesh points of V are shown as red closed disks. Pyramid (1, 0) + P₈ is completely filled by V; the line i + j = 10 has three additional points from V. The R(V) = 12 neighbours are shown as blue circles. The dashed lines represent the points with i - j = 1 and i + j = 10, respectively.</figcaption></figure>

3.3 Case T = 0

We give a brief specific proof of the optimality of ball-like shapes in two dimensions, based on
the general proof by Wang and Wang [21] for any number of dimensions. Since V does not
touch any border, we can use the whole plane and take the origin as the centre of the basic balls
considered. (We number this way only in this subsection, i.e., for the case T = 0.)

Define ball $B_r^0$ by

$$
B_r^0 = B_r(0,0) = \{(i,j) : |i| + |j| \le r\}. \tag{6}
$$

cf. Eqn. (1). Here, we limit ourselves to the general case $r \ge 1$. We create ball-like shapes by
adding up to three borders to the basic ball, as follows. Define

$$
B_r^1 = B_r^0 \cup \{(-r, 1), (-r+1, 2), \dots, (-1, r)\},
$$

$$
B_r^2 = B_r^1 \cup \{(0, r+1), (1, r), \dots, (r, 1)\},
$$

$$
B_r^3 = B_r^2 \cup \{(r+1, 0), (r, -1), \dots, (1, -r)\}.
$$

Figure 11 shows the four shapes for $r = 2$.

Let $\phi_0$ be the function denoting the cardinality of these sets, with $\phi_0(4r+q) = |B_r^q|$ for $r \ge 1$
and $q = 0, 1, 2, 3$. Therefore, for $k = 4r+q$ with $0 \le q \le 3$ we have

$$
\phi_0(k) = \begin{cases} 2r^2 + 2r + 1 = (k^2 + 4k + 8)/8 & \text{if } q = 0, \\ 2r^2 + 3r + 1 = (k^2 + 4k + 3)/8 & \text{if } q = 1, \\ 2r^2 + 4r + 2 = (k^2 + 4k + 4)/8 & \text{if } q = 2, \\ 2r^2 + 5r + 3 = (k^2 + 4k + 3)/8 & \text{if } q = 3. \end{cases} \tag{7}
$$

Note that adding a fourth border consisting of the set {$(0, -r - 1), (-1, -r), \dots, (-r - 1, 0)$}
would give ball $B_{r+1}^0$ with $(2r^2 + 5r + 3) + (r + 2) = 2(r + 1)^2 + 2(r + 1) + 1$ points. It can
straightforwardly be verified that

$$
R(B_r^q) = 4r + 4 + q.
$$

It will be furthermore convenient to introduce a rectangular version of a ball,

$$
B_{abcd} = \{(i,j) : a \le i + j \le b \land c \le i - j \le d\},
$$

for integers *a*, *b*, *c*, *d* with *a* < *b* and *c* < *d*. (We exclude the cases *a* = *b* and *c* = *d* because then the ball is not connected.) An example is shown in Figure 12.
<figure><img src="image_16.png" /><figcaption>Figure 11: Ball-like shapes $B_2^q$ for $q = 0, 1, 2, 3$, with 13, 15, 18, 21 points, respectively, shown as red closed disks, with 12, 13, 14, 15 neighbours, respectively, shown as blue circles. The added points are marked by a cross. The shapes do not touch any borders.</figcaption></figure>

The *parity* of a number $a$ is defined as 0 if $a$ is even, and 1 if $a$ is odd. The parities of $a, b, c, d$ determine how the following cardinality count formula should be rounded.

**Lemma 3.8.** Let $a < b$ and $c < d$. Then

$$|B_{abcd}| = (b - a + 1)(d - c + 1)/2 + \delta.$$

where the rounding parameter $\delta$ is given by

$$\delta = \begin{cases} 0 & \text{if parity}(a) \neq \text{parity}(b) \lor \text{parity}(c) \neq \text{parity}(d), \\ 1/2 & \text{if parity}(a) = \text{parity}(b) = \text{parity}(c) = \text{parity}(d), \\ -1/2 & \text{if parity}(a) = \text{parity}(b) \neq \text{parity}(c) = \text{parity}(d). \end{cases} \quad (8)$$

Furthermore, the number of neighbours of $B_{abcd}$ is

$$R(B_{abcd}) = b - a + d - c + 4.$$

*Proof.* $B_{abcd}$ is contained in $b - a + 1$ wavefronts consisting of points $(i, j)$ with $i + j = k$, each restricted to a segment of points by the condition $c \le i - j \le d$. For a wavefront segment corresponding to values $i + j = k$, the condition $c \le i - j \le d$ is equivalent to $(k + c)/2 \le i \le (k + d)/2$. In case $c$ and $d$ have a different *parity*, i.e., $c$ is even and $d$ is odd or vice versa, all
<figure><img src="image_17.png" /><figcaption>Figure 12: Rectangular ball $B_{abcd}$ with $a = -2$, $b = 2$, $c = -3$, and $d = 3$. The 17 mesh points of $V$ are shown as red closed disks. The $R(V) = 14$ neighbours of $V$ are shown as blue circles.</figcaption></figure>

segments have $(d-c+1)/2$ points, so $|B_{abcd}| = (b-a+1) \cdot (d-c+1)/2$, which corresponds to $\delta = 0$.

We investigate the remaining cases, in which $c$ and $d$ have the same parity. Here, either both limits of the segment, i.e., $i = (k+c)/2$ and $i = (k+d)/2$, are integer and hence their corresponding points are included in the segment, or both corresponding points are excluded. This implies that the segments alternatingly contain $(d-c)/2+1$ points and $(d-c)/2$ points.

In case $a$ and $b$ have a different parity, the number of segments, $b-a+1$, is even. By counting segments two by two, we see that each pair has $d-c+1$ points, and thus $|B_{abcd}| = \frac{1}{2}(b-a+1) \cdot (d-c+1)$, which also corresponds to $\delta = 0$.

In case $a$ and $b$ have the same parity, the number of segments is odd. In that case, the first $b-a$ segments contain a total of $\frac{1}{2}(b-a) \cdot (d-c+1)$ points and the last segment (i.e., with $k=b$) contains $(d-c)/2+1$ points if $a$ and $c$ have the same parity, and $(d-c)/2$ points otherwise. This corresponds to $\delta = 1/2$ and $\delta = -1/2$, respectively.

The neighbours of $B_{abcd}$ are exactly the points in $B_{a-1,b+1,c-1,d+1} \setminus B_{abcd}$. Because all parities flip when moving from $B_{abcd}$ to $B_{a-1,b+1,c-1,d+1}$, the parity conditions in (8) and hence the rounding stay the same. Therefore,

$$R(B_{abcd}) = \frac{1}{2}[(b-a+3)(d-c+3) - (b-a+1)(d-c+1)] = b-a+d-c+4$$

□

A special case of Lemma 3.8 is $B_{-r,r,-r,r} = B_r^0$ which has $(2r+1)^2/2 + 1/2 = 2r^2 + 2r + 1$ points and $2r + 2r + 4 = 4r + 4$ neighbours. More in general, we have that

$$B_r^0 = B_{-r,r,-r,r},$$

$$B_r^1 = B_{-r,r,-r-1,r},$$

$$B_r^2 = B_{-r,r+1,-r-1,r},$$

$$B_r^3 = B_{-r,r+1,-r-1,r+1}.$$

We formulate the following lemma on the optimal shape of a vertex set without reference to a mesh, because the vertex set touches no borders. The result holds for any particular mesh provided that the set indeed touches no border.
**Lemma 3.9.** Let $V$ be a part with $n = |V| > 5$ mesh points and $T(V) = 0$. Let $k$ be such that $\phi_0(k) < n \le \phi_0(k+1)$. Then

$$R(V) \ge k + 5.$$

The lower bound $R(V) = k+5$ is attained by a set of mesh points $S$ consisting of the $\phi_0(k)$ points of the ball-like shape $B_r^q$, where $r = [k/4]$ and $q = k \mod 4$, and the first $n - \phi_0(k)$ points from $B_r^{q+1}$ for $q < 3$ and from $B_{r+1}^0$ for $q = 3$. Here, the order of these additional points is given by the clockwise addition of new points when moving from $B_r^q$ to $B_r^{q+1}$ or $B_{r+1}^0$.

*Proof.* Let $V$ be a connected vertex set in the plane with $|V| > 5 = \phi_0(4)$. Define

$$a = \min \{i + j : (i, j) \in V\},$$

$$b = \max \{i + j : (i, j) \in V\},$$

$$c = \min \{i - j : (i, j) \in V\},$$

$$d = \max \{i - j : (i, j) \in V\}.$$

Note that $a < b$ and $c < d$, because otherwise $V$ would be contained in one wavefront, which is unconnected for $|V| > 1$.

Because for all $(i, j) \in V$, we have that $a \le i + j \le b$ and $c \le i - j \le d$, it follows that

$$V \subseteq B_{abcd}.$$

As a consequence, $|V| \le |B_{abcd}| = (b - a + 1)(d - c + 1)/2 + \delta$, where $\delta$ is given by Eqn (8).

We will use the property

$$\min\{x + y : x, y \in \mathbb{R} \wedge x, y > 0 \wedge xy = m\} = 2\sqrt{m}, \qquad (9)$$

for the choice $x = b - a + 1$, $y = d - c + 1$, and $m = 2(|B_{abcd}| - \delta)$.

Let $k$ be such that $\phi_0(k) < n \le \phi_0(k+1)$. Then $x+y \ge k+3$ must hold, because otherwise, if $x+y \le k+2$, then by Eqn (9) also $2\sqrt{m} \le k+2$, so $m \le (k+2)^2/4$. But since $n = |V| \le m/2+\delta$, we have

$$n \le \frac{(k+2)^2}{8} + \delta \le \frac{(k+2)^2}{8} + \frac{1}{2} = \frac{k^2 + 4k + 8}{8},$$

which conflicts with the choice of

$$n \ge \phi_0(k) + 1 \ge \frac{k^2 + 4k + 11}{8},$$

where the latter bound corresponds to the cases $q = 1, 3$ in the definition of $\phi_0$ given by Eqn (7).

From $x+y \ge k+3$, it then follows that $(b-a+1)+(d-c+1) \ge k+3$ and hence we obtain the inequality

$$b - a + d - c \ge k + 1.$$

This inequality is crucial, as it will lead to the desired result if we can prove that $R(V) \ge b - a + d - c + 4$.

Take points $\mathbf{a} = (a_1, a_2) \in V$ with $a_1 + a_2 = a$, $\mathbf{b} = (b_1, b_2) \in V$ with $b_1 + b_2 = b$, $\mathbf{c} = (c_1, c_2) \in V$ with $c_1 - c_2 = c$, $\mathbf{d} = (d_1, d_2) \in V$ with $d_1 - d_2 = d$. Note that $c_1 \le (b+c)/2$, because $(c_1, c_2) \in V$ implies $c_1+c_2 \le b$. Similarly, $b_1 \ge (b+c)/2$, so that we have $c_1 \le b_1$. In the same way, we note that $a_1 \le d_1$, $d_2 \le b_2$, and $a_2 \le c_2$. The four points are shown in Figure 13.
<figure><img src="image_18.png" /><figcaption>Figure 13: A part V of 37 mesh points that touches no border. The mesh points of V are shown as red closed disks. The dashed lines represent mesh points with $i + j = a = -4$, $i + j = b = 7$, $i - j = c = -3$, and $i - j = d = 4$, respectively. A point $\mathbf{a} = (a_1, a_2) \in V$ is chosen on line $i+j=a$, and a point $\mathbf{b} = (b_1, b_2) \in V$ on line $i+j=b$. Similarly, points $\mathbf{c}$ and $\mathbf{d}$ are chosen. The $R(V) = 23$ neighbours of V are shown as blue circles. Using the points $\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}$, the neighbour sets $N_1, N_t, N_r, N_b$ can be formed, which are shown by the points marked ‘l’, ‘t’, ‘r’, ‘b’, with 5, 6, 6, and 5 points, respectively, giving a lower bound $R(V) \ge 22$.</figcaption></figure>

Define the following sets of neighbours of V, corresponding to topmost, rightmost, bottommost, and leftmost neighbours, respectively:

$$ 
\begin{aligned}
N_t &= \{(i, t(i) + 1) : c_1 \le i \le b_1\}, \\
N_r &= \{(r(j) + 1, j) : d_2 \le j \le b_2\}, \\
N_b &= \{(i, b(i) - 1) : a_1 \le i \le d_1\}, \\
N_l &= \{(l(j) - 1, j) : a_2 \le j \le c_2\}.
\end{aligned}
$$

The set $N_t$ is the set of topmost neighbours in the columns from $c_1$ to $b_1$. Its cardinality is $|N_t| = b_1 - c_1 + 1$ because every column of the set has a topmost neighbour, owing to the existence of a path from $\mathbf{c}$ to $\mathbf{b}$. The four sets are illustrated in Figure 13.

These sets are disjoint. The proof that $N_t \cap N_r = \emptyset$ is similar to that of Lemma 3.2, which we will not repeat. The same holds for $N_r \cap N_b = \emptyset$, $N_b \cap N_l = \emptyset$, $N_l \cap N_t = \emptyset$. The proof that $N_l \cap N_r = \emptyset$ is different, but it is easy to see that in a nonempty row, the leftmost neighbour and the rightmost neighbour cannot be the same. The proof that $N_t \cap N_b = \emptyset$ is similar.

The total number of neighbours of V is then

$$ 
\begin{aligned}
R(V) &\ge |N_t| + |N_r| + |N_b| + |N_l| \\
&= (b_1 - c_1 + 1) + (b_2 - d_2 + 1) + (d_1 - a_1 + 1) + (c_2 - a_2 + 1) \\
&= (b_1 + b_2) - (a_1 + a_2) + (d_1 - d_2) - (c_1 - c_2) + 4 \\
&= b - a + d - c + 4.
\end{aligned}
$$
<figure><img src="image_19.png" /><figcaption>Figure 14: A part V of 13 mesh points on a 7 × 5 mesh. The mesh points of V are shown as red closed disks. The hull H(V) is shown as a red rectangle. The R(V) = 5 neighbours are shown as blue circles. The number of touched borders is T(V) = 3.</figcaption></figure>

This establishes the lower bound of the lemma.

Finally, we will prove that an extended ball-like shape S attains the bound. For a number of points n that satisfies $\phi_0(k) < n \le \phi_0(k+1)$, we define $s = n - \phi_0(k)$. If $k \bmod 4 = 0$, we take $r = k/4$ and then define S by

$$S = B_r^0 \cup \{(-r, 1), (-r+1, 2), \dots, (-r+s-1, s)\}.$$

This increases the number of neighbours of $B_r^0$ from $4r + 4$ to $4r + 5$, so $R(S) = 4r + 5 = k + 5$. Similarly, if $k \bmod 4 = 1$ we take $r = (k-1)/4$, then extend $B_r^1$ by s points, thereby increasing the number of neighbours to $4r + 6 = k + 5$. The cases $k \bmod 4 = 2, 3$ are similar. □

## 3.4 Case T = 3

Recall that we have an $I \times J$ mesh.

**Lemma 3.10.** Let V be a part with $T(V) = 3$, and let the nontouched border be the right border. Then

$$R(V) \ge J.$$

*Proof.* Every row j with $0 \le j < J$ has a point in V because there exists a path from the bottom border to the top border. Every row also has a neighbouring point to the right of V, since V does not touch the right border. Thus, V has at least J neighbours. □

The optimal value for this case is $R(V) = J$, since we attain the lower bound for a part V with $n = |V|$ points, where columns 0, ..., $\lfloor n/J \rfloor - 1$ of the mesh are entirely included in V, and the bottom n mod J points of the next column are also included, see Figure 14.

## 3.5 Case T = 4

### 3.5.1 Dropping operation

To prove optimality for general subsets V of mesh points, it is useful to be able to transform a subset V into another subset V' with the same number of mesh points and a smaller or equal neighbour count, and with a more beneficial structure such as dense rows or columns at the borders of the mesh. The following dropping operation is such a transformation.

For a subset of mesh points V, not necessarily connected, define the transformed subset

$$Drop_b(V) = \{(i, j) : 0 \le i < I \land 0 \le j < c_i\},$$
<figure><img src="image_20.png" /><figcaption>Figure 15: A subset V of 15 mesh points and its transformation $V' = Drop_b(V)$. The mesh points are shown as red closed disks and their neighbours as blue circles. The number of neighbours reduces from $R(V) = 32$ to $R(V') = 15$.</figcaption></figure>

where $c_i \ge 0$ is the number of elements of V in column i. The transformation is carried out by dropping all elements of V in the different columns straight down to the bottom. The dropping operation to the bottom is illustrated in Figure 15. Similarly, we can define $Drop_t(V)$, $Drop_1(V)$, $Drop_r(V)$ for droppings towards the top, left, and right border, respectively.

**Lemma 3.11.** Let V be a subset of mesh points and let $V' = Drop_b(V)$. Then $|V'| = |V|$ and $R(V') \le R(V)$. Furthermore, if V is connected, then so is $V'$.

*Proof.* The set $V'$ has the same number of points as V, because the number of points in each column does not change by the dropping transformation.

To establish $R(V') \le R(V)$, we show that the number of neighbours in column i can only decrease or stay the same by the transformation. Consider column i. If it is dense, it contains no neighbours of V, and the transformation does not change it, so the transformed column i contains no neighbours of $V'$. Otherwise, if the column is not dense, the number $n_i$ of neighbours of V in column i satisfies

$$n_i \ge \max\{c_{i-1} - c_i, c_{i+1} - c_i, \min\{c_i, 1\}\}, \quad (10)$$

because if $c_{i-1} > c_i$, column i must contain at least $c_{i-1} - c_i$ neighbours of points of V in column $i-1$, and similar for column $i+1$. Here, we define $c_{-1} = c_I = 0$, so that the boundary columns are treated correctly. Furthermore, since column i is not dense, it must contain at least one neighbour if it is nonempty, i.e., if $c_i \ge 1$.

The number $n'_i$ of neighbours of $V'$ in column i attains the lower bound of Eqn (10),

$$n'_i = \max\{c_{i-1} - c_i, c_{i+1} - c_i, \min\{c_i, 1\}\},$$

because if $c_{i-1} > c_i$, column i contains exactly $c_{i-1} - c_i$ neighbours of points of V in column $i-1$, and similar for column $i+1$. If both adjacent columns contribute neighbours, they will overlap and the largest column will determine the neighbour count. If column i is nonempty, the point $(i, c_i)$ will be a neighbour in any case. In the example of Figure 15 with $c_0 = 0$, $c_1 = 3$, and $c_2 = 3$, the number of neighbours in column 1 decreases from $n_1 = 4$ to $n'_1 = \max\{-3, 0, 1\} = 1$.

If V is connected and hence a part, there is a path from a leftmost point $(i, j) \in V$ to a rightmost point $(i', j') \in V$, where $i \le i'$. This implies that all columns $i, \dots, i'$ have a point in V, and hence $(i, 0), \dots, (i', 0) \in V'$. All these points are connected in $V'$. The remaining
points, in rows $j > 0$, are connected to these points because the points of $V'$ in each column are contiguous. This means that $V'$ is connected as well and hence is a legitimate part.

□

Dropping is a form of compression [7], where a subset $V$ is transformed into a subset $V'$ with the same cardinality and a reduced number of neighbours. Bollobás and Leader [7] define $i$-compression, where $i$ stands for the direction of the compression on a multidimensional infinite grid, such that $Drop_1$ is 1-compression and $Drop_b$ is 2-compression.

Using a term from the order theory of sets, we call $V$ a down-set if $(i, j) \in V$, $0 \le i' \le i$, and $0 \le j' \le j$ together imply that $(i', j') \in V$. An equivalent definition is that the points of $V$ in each column form a contiguous block touching the bottom border and those in each row form a contiguous block touching the left border.

**Lemma 3.12.** Let $V$ be a subset of mesh points and let $V' = Drop_b(V)$ and $V'' = Drop_1(V')$. Then $V''$ is a down-set.

*Proof.* We only have to prove that the points of $V''$ in column $i$ form a contiguous block touching the bottom border, because the similar statement for row $j$ is true by construction, the last dropping operation being to the left. Now, let $c_i$ be the number of points of $V$ in column $i$ and $r_j$ be the number of points of $V'$ in row $j$. Then,

$$r_j = |\{i : 0 \le i < I \wedge c_i > j\}|,$$

because $(i, j) \in V'$ exactly if $(i, j)$ is one of the points $(i, 0), \dots, (i, c_i - 1)$. Note that $r_0 \ge r_1 \ge \dots \ge r_{J-1}$. By the definition of dropping $V'$ to the left, we have

$$V'' = \{(i, j) : 0 \le j < J \wedge 0 \le i < r_j\}.$$

Let $(i, j) \in V''$ and let $j' < j$. We are done if we can prove that $(i, j') \in V''$ as well. But this follows from $i < r_j \le r_{j'}$. □

### 3.5.2 Case $T = 4$ with dense rows or columns

In this subsection, we will examine the case where $V$ touches four borders and has at least one dense row or column. Here, wlog we assume that $I \ge J$.

Define L-shape $L_k$ for $0 \le k \le I + J - 2$ by

$$L_k = \{(i, j) : 0 \le i < I \wedge 0 \le j < J \wedge (i = 0 \vee j = 0 \vee i + j \le k)\}. \quad (11)$$

Define the function denoting the number of points of $L_k$ by

$$\phi_4(k) = \begin{cases} I + J - 1 + \frac{(k-1)k}{2} & \text{if } 0 \le k \le J, \\ I + (J-1)(k+1 - J/2) & \text{if } J \le k \le I, \\ IJ - (I + J - k - 2)(I + J - k - 1)/2 & \text{if } I \le k \le I + J - 2. \end{cases} \quad (12)$$

The count of the number of points for the first case is based on $I + J - 1$ points in row 0 and column 0, and $1 + 2 + \dots + (k-1) = (k-1)k/2$ points for the wavefronts $W_2, \dots, W_k$ excluding the points from row 0 and column 0. Figure 16 illustrates this case. For the intermediate case, we count $I + J - 1 + (J-1)J/2 + (k - J)(J - 1)$ points, because every additional wavefront beyond $k = J$ adds $J - 1$ points, as $I \ge J$. For the last case $k \ge I$, we count the whole mesh of $IJ$ points and subtract the number of points $(i, j)$ with $i + j \ge k + 1$. Note that $\phi_4(k)$ is well-defined for the case $k = J$, because then the first and second formula yield the same value; for $k = I$, the second and third formula yield the same value. This double definition at case boundaries is useful and it will give us some flexibility in certain proofs later on.
<figure><img src="image_21.png" /><figcaption>Figure 16: L-shape $V = L_4$ with 18 mesh points on a 7 × 6 mesh. The mesh points of $V$ are shown as red closed disks. The $R(V) = 7$ neighbours are shown as blue circles. The dashed line represents mesh points with $i + j = 4$.</figcaption></figure>

**Lemma 3.13.** Let $I \ge J$. Let $V$ be a part with $n = |V|$ mesh points and $T(V) = 4$, where at least one row or column is dense. Let $k$ be such that $\phi_4(k) \le n < \phi_4(k+1)$. Then

$$R(V) \ge I + J - k - 2.$$

The lower bound $R(V) = I + J - k - 2$ is attained by a set of mesh points $S$ consisting of the $\phi_4(k)$ points of the shape $L_k$ and the lowest $s = n - \phi_4(k)$ points $(i, j)$ with $i + j = k + 1$.

*Proof.* First, assume that $V$ has a dense row. Let $V' = \text{Drop}_1(V)$. Because $V$ touches the top and bottom border and $V$ is connected, every row has a point in $V$, and hence column 0 of $V'$ is dense. If there are other dense columns in $V'$, they are adjacent to column 0, giving a contiguous block of dense columns at the left border. The remaining columns are not dense. Note that $V'$ also has a dense row because $V$ has one. Now, let $V'' = \text{Drop}_b(V')$. This creates a contiguous block of dense rows at the bottom. Thus, we have a contiguous block of at least one dense row at the bottom border, a contiguous block of at least one dense column at the left border, and no further dense rows or columns.

Second, if $V$ has no dense row but it has a dense column, then we create $V' = \text{Drop}_b(V)$ and $V'' = \text{Drop}_1(V')$. The result is again a contiguous block of dense rows at the bottom, a block of dense columns at the left, and no further dense rows or columns.

Because of Lemma 3.11, we have that $|V''| = |V|$ and $R(V'') \le R(V)$. We are done if we prove that $R(V'') \ge I + J - k - 2$. Assume that the contiguous block of rows at the bottom contains $r$ rows with $r \ge 1$, and that the contiguous block of columns at the left contains $c$ columns with $c \ge 1$.

Now, we define two sets of neighbours of $V''$,

$$N_t = \{(i, t(i) + 1) : c \le i < I\},$$

$$N_r = \{(r(j) + 1, j) : r \le j < J\}.$$

Note that we make a distinction between the function $r(\cdot)$, which gives the rightmost point in a row, and the number $r$ of dense rows. In Figure 16, all neighbours except (1, 5) belong to $N_t$, and all except (5, 1) and (6, 1) belong to $N_r$. The number of receives of $V''$ can be bounded as

$$R(V'') \ge |N_t| + |N_r| - |N_t \cap N_r|.$$

The neighbours from $N_t$ and $N_r$ all lie within the mesh, because the points of $V''$ in columns $i \ge c$ do not touch the top border, so $t(i) < J - 1$ for all $i$, and those in rows $j \ge r$ do not touch the right border, so $r(j) < I - 1$ for all $j$.
Let

$$N_{\text{tr}} = N_t \cap N_r \text{ and } m = |N_{\text{tr}}|.$$

If we have two distinct points $(i, j)$, $(i', j') \in N_{\text{tr}}$, then $i \neq i'$ and $j \neq j'$ must hold. Otherwise, assuming wlog that $i = i'$, we have $j = t(i) + 1 = t(i') + 1 = j'$, so the points are the same.

By considering the points from $N_{\text{tr}}$ in strictly increasing order of their column index $i$, we deduce that there must be a nondense row $j$ with at least $c$ points in $V''$ (namely, at least those points in the dense column block), another nondense row with at least $c+1$ points in $V''$, etc., until we have a nondense row with $c+m-1$ points in $V''$. This is a consequence of the pigeonhole principle and our result that points in $N_{\text{tr}}$ do not have common coordinates. It holds that $m \ge 1$, since $(i_0, t(i_0) + 1) \in N_{\text{tr}}$, where $i_0 = \min\{i : \exists j \text{ with } (i, j) \in N_r\}$, owing to $V''$ being a down-set. The only exception is the case where $V$ equals the whole mesh; in that case the lemma is true with $k = I + J - 2$, where for convenience we define $\phi_4(I + J - 1) = \infty$.

The total number of points of $V''$ is then at least $c+(c+1)+\cdots+(c+m-1)$ for the $m$ rows with a point in $N_{\text{tr}}$, plus $(J-m)c+(I-c)r$ for the remaining points in dense rows or columns. Therefore,

$$n = |V''| \ge c + (c + 1) + \cdots + (c + m - 1) + (J - m)c + (I - c)r. \quad (13)$$

We now perform a case-by-case analysis on the values of $r+c+m-1$ to bound $m$ using Eqn (13).

**Case 1** ($r+c+m-1 \le J$): We obtain lower bounds for the last two terms of Eqn (13):

$$\begin{aligned} (J - m)c &= J - m + (J - m)(c - 1) \\ &\ge J - m + (r - 1 + c)(c - 1), \\ &\ge J - m + (r - 1)(c - 1) + 1 + 2 + \cdots + (c - 1). \end{aligned}$$

In the last inequality, we used the fact that $c(c-1) = 2(1+2+\cdots+(c-1))$.

Because $J \le I$, we also have $r+c+m-1 \le I$, so that

$$\begin{aligned} (I - c)r &= I - c + (I - c)(r - 1) \\ &\ge I - c + (m - 1 + r)(r - 1) \\ &\ge I - c + (m - 1)(r - 1) + 1 + 2 + \cdots + (r - 1) \\ &= I - c - c(r - 1) + (c + m) + (c + m + 1) + \cdots + (c + m + r - 2). \end{aligned}$$

In the last equality, we added $c+m-1$ to the $r-1$ terms of the sum $1+2+\cdots+(r-1)$.

By combining the two resulting bounds with Eqn (13) and simplifying, we obtain

$$\begin{aligned} n &\ge 1 + 2 + \cdots + (c + m + r - 2) + J - m + (r - 1)(c - 1) + I - c - c(r - 1) \\ &= (I + J - 1) + 1 + 2 + \cdots + (c + m + r - 3) \\ &= \phi_4(r + c + m - 2). \end{aligned}$$

**Case 2.** ($J < r + c + m - 1 \le I$): Define $c' = r + c + m - 1 - J$, which implies $c' > 0$. Furthermore, $c' < c$ because $r + m \le J$. Consider the $(I - c') \times J$ submesh consisting of the columns $i = c', \dots, I-1$ of the $I \times J$ mesh. Note that $I - c' \ge J$ because $r + c + m - 1 \le I$. Therefore, the width of the submesh is at least its height, just as we have $I \ge J$ in the original mesh. The number of points of $V''$ on the submesh is $n - c'J$. The first $c - c' \ge 1$ columns and the first $r \ge 1$ rows of this submesh are dense. This means that we can apply the results of Case 1 on the submesh, because $r + (c - c') + m - 1 = J$. To avoid confusion, we will mark $\phi_4$ with a superscript denoting the submesh size. This leads to

$$\begin{aligned} n &\ge c'J + \phi_4^{(I-c') \times J} (r + (c - c') + m - 2) \\ &= c'J + I - c' + J - 1 + (J - 2)(J - 1)/2. \end{aligned}$$
Here, we used the fact that $r+c-c'+m-2=J-1$. This leads to

$$ 
\begin{aligned}
n &\ge I + (J-1)(c' + 1 + (J-2)/2) \\
&= I + (J-1)(r + c + m - 1 - J + J/2) \\
&= \phi_4(r + c + m - 2).
\end{aligned}
$$

For the last equality, we applied the second formula of Eqn (12).

**Case 3.** ($r+c+m-1>I$): Define $r' = r+c+m-1-I$, which implies $r' > 0$. Furthermore, $r' < r$ because $c+m \le I$. Consider the $I \times (J-r')$ submesh consisting of the rows $j = r', \dots, J-1$ of the $I \times J$ mesh. Note that $I \ge J > J-r'$. Therefore, the width of the submesh is larger than its height. The number of points of $V''$ on the submesh is $n-r'I$. The first $c \ge 1$ columns and the first $r-r' \ge 1$ rows of this submesh are dense. This means that we can apply the results of Cases 1 and 2, because $(r-r') + c + m - 1 = I$. Thus, we obtain

$$ 
\begin{aligned}
n &\ge r'I + \phi_4^{I \times (J-r')}((r-r') + c + m - 2) \\
&= r'I + \phi_4^{I \times (J-r')}(I - 1).
\end{aligned}
$$

Because $J-r' \le I-1 \le I$, we can apply the second formula of Eqn (12), which yields

$$ 
\begin{aligned}
n &\ge r'I + I + (J - r' - 1)(I - (J - r')/2) \\
&= IJ - (J - r' - 1)(J - r')/2 \\
&= IJ - (I + J - (r + c + m))(I + J - (r + c + m) + 1) \\
&= \phi_4(r + c + m - 2).
\end{aligned}
$$

Here, we used the fact that $r+c+m-2 \ge I$, so that the third formula of Eqn (12) is applicable.

As a result of Cases 1, 2, 3, we have $\phi_4(k+1) > n \ge \phi_4(r+c+m-2)$. Because $\phi_4$ is strictly monotonically increasing, we have as a consequence that $k \ge r+c+m-2$.

The number of receives for $V''$ is at least

$$ R(V'') \ge |N_t| + |N_r| - |N_{tr}| = I - c + J - r - m \ge I + J - k - 2. $$

This proves the first statement of the lemma.

The lower bound is attained by $L_k$ for $n = \phi_4(k)$ with $k < J$, which can be seen simply by enumerating the neighbours: first $(1, J-1)$, $(1, J-2)$, ..., $(1, k)$, then $(2, k-1)$, $(3, k-2)$, ..., $(k, 1)$, and finally $(k+1, 1)$, ..., $(I-1, 1)$, giving a total of $I + J - k - 2$ neighbours. Adding the $s$ given points does not change $R(V)$ as long as these points do not fill the whole wavefront $W_{k+1}$, which is equivalent to $n = \phi_4(k) + s < \phi_4(k+1)$. For the cases $J \le k < I$ and $k \ge I$, the bound is also attained, which can be seen again by enumeration. This proves the second statement of the lemma. $\square$

The shapes $L_k$ are not the unique optimal solutions, since there exist others: for instance, we can add the $s$ points in row 1 to the right starting at $(k, 1)$, provided $k+s \le I$.

### 3.5.3 Case $T=4$ without dense rows or columns

The case that remains for a part with $T=4$ is the case where no row or column is dense. We have some computational evidence that the bound of Lemma 3.13 also holds for this case, but we do not have a proof. The evidence concerns the problem of a $16 \times 16$ mesh with $n=64$ and with limited imposition of connectivity. This problem was found to have an optimal solution $V$ with $R(V) = 22$, where $V$ happens to be connected. This result exactly fits the lemma.

The fact that there are no dense rows or columns does however provide us with another, weaker bound. This bound is in fact the same as for the case $T=3$.
**Lemma 3.14.** Let $V$ be a part with $T(V) = 4$, where no row or column is dense. Then

$$R(V) \geq \max\{I, J\}.$$

*Proof.* Assume wlog that $I \geq J$. Every column $i$ has a point in $V$ because there is a path in $V$ from the left to the right border. Furthermore, every column $i$ has a point not in $V$, because no column is dense. Therefore, every column contains a neighbour of $V$, and hence there are at least $I$ neighbours. $\square$

# 4 Using the theoretical findings

In this section we put the theoretical findings developed so far into use. First, we certify that a previously claimed result is optimal. Second, we develop heuristic approaches informed by the theory.

## 4.1 Optimal partitioning of a square 16 × 16 mesh into 4 parts

It was claimed previously [2] that an optimal 4-way partitioning of the 16 × 16 mesh had a total communication volume of 57. We show that this is true. We will do this first by deriving a lower bound $R(V) \geq 12$ on the number of receives per part $V$, by considering the five different cases $T(V) = 0, 1, 2, 3, 4$ separately. Then we will combine the individual cases.

### 4.1.1 Individual cases

**Case T = 0:** Here, $V$ does not touch any border. For $n = |V| = 64$, by using the definition (7) of the function $\phi_0(\cdot)$, we have $61 = \phi_0(20) < n \leq \phi_0(21) = 66$, so that Lemma 3.9 with $k = 20$ gives a lower bound $R(V) \geq k + 5 = 25$.

**Case T = 1:** Here, part $V$ touches one border. Let us assume in this case wlog that the touched border is the bottom border. For $n = |V| = 64$, by using the definition (3) of the function $\phi_1(\cdot)$, we have $56 = \phi_1(13) < n \leq \phi_1(14) = 64$, so that Lemma 3.7 with $k = 13$ gives a lower bound $R(V) \geq k + 4 = 17$. However, because the mesh is too small, this lower bound cannot be obtained and we have $R(V) \geq 18$, which can be seen by examining the proof of Lemma 3.7 as we do below. Let $a$ and $b$ as given by Eqn (4). We then have by Eqn (5) that $V \subseteq (a, 0) + P_{b-a}$ and hence $|V| \leq \phi_1(b-a)$. Therefore, $b-a \geq 14$ must hold. If $b-a = 14$, we have $|V| = 64 = \phi_1(b-a) = |P_{b-a}|$ so the sets $V$ and $(a, 0) + P_{b-a}$ must be the same. But then the bottom row of $V$ has 15 points and it must touch either the left or the right border. As a consequence, $b-a \geq 15$, and by the proof of Lemma 3.7, this implies $R(V) \geq b-a+3 \geq 18$.

**Case T = 2:** Here, part $V$ touches two borders. If these are nonadjacent, we have $R(V) \geq 32$ by Lemma 3.1. Now assume that the touched borders are adjacent. Let us assume in this case wlog that the touched borders are the left and bottom borders. For $n = |V| = 64$, by using the definition (2) of the function $\phi_2(\cdot)$, we have $55 = \phi_2(9) < n \leq \phi_2(10) = 66$ so that Lemma 3.3 with $k = 9$ gives a lower bound $R(V) \geq 12$. This bound can be attained, see for instance the top-left (blue) part and the bottom-right (black) part in Figure 17.

**Case T = 3:** Lemma 3.10 with $I = J = 16$ and $|V| = 64$ states that $R(V) \geq 16$.

**Case T = 4:** For $n = |V| = 64$, by using the definition (12) of the function $\phi_4(\cdot)$, we have $59 = \phi_4(8) \leq n < \phi_4(9) = 67$, so that if $V$ has a dense row or column, then Lemma 3.13 with $k = 8$ gives a lower bound $R(V) \geq I + J - k - 2 = 22$ that can be attained. If there is no dense row or column, Lemma 3.14 gives a lower bound $R(V) \geq 16$. Hence, $R(V) \geq 16$.
<figure><img src="image_22.png" /><figcaption>Figure 17: An optimal solution for partitioning a 16 × 16 mesh into four equal-sized parts. The colour of a mesh point depicts the part to which it is assigned. The communication volume of the solution is $C = 57$. The top-left (blue) and bottom-right (black) parts each have 12 receives, the bottom-left (red) part has 17, and the top-right (yellow) part 16.</figcaption></figure>

### 4.1.2 Combining the individual cases

We now put the results aforementioned case-by-case analysis together to prove that $C = 57$ is optimal for a 4-way partitioning of an 16 × 16 mesh. One such solution is shown in Figure 17.

The results for the cases $T(V)=0-4$ show that the minimum number of receives of a part is 12. Let us define the surplus of a part $V$ as $R(V) - 12$. The total surplus is then $S = C - 48$, i.e., the surplus of the four parts. We will prove that no partitioning exists with $S \le 8$, i.e., cost less than or equal to 56. This proves that a solution with cost 57 is indeed optimal.

If a part $V$ has $T(V) = 0$, we must have $S \ge 25 - 12 = 13$, so the solution cannot be optimal. Thus, in an optimal solution, all parts must touch at least one border.

If a part $V$ has $T(V) = 1$, this part cannot contain a corner of the mesh, and hence three parts must contain four corners. Therefore, another part $V' \neq V$ must contain at least two corners and hence $T(V') \ge 3$. This implies $R(V') \ge 16$ as explained in the case analysis above. So together with $R(V) \ge 18$ we get $S \ge 18 + 16 - 24 = 10$, and hence the solution cannot be optimal. Thus, in an optimal solution, all parts must touch at least two borders.

If a part $V$ has $T(V) = 2$ in an optimal solution, these must be adjacent, because otherwise $S \ge 32 - 12 = 20$. If $V$ does not contain the corresponding corner, then by Lemma 3.4 we can increase the lower bound on its number of neighbours. For $n = |V| = n' = |V'| = 64$, we have $120 = \phi_2(14) < n + n' \le \phi_2(15) = 136$, and $\lfloor \sqrt{n'} \rfloor = 8$, so $R(V) \ge 14 + 3 + 8 = 25$. Therefore, we must have $S \ge 25 - 12 = 13$, so that the solution cannot be optimal. Thus, in an optimal solution, all parts that touch two borders must touch two adjacent borders, and they must include the corresponding corner.

If a part $V$ has $T(V) = 3$, but does not contain both corresponding corners, then by an argument as in the proof of Lemma 3.4 we can increase the lower bound on its number of neighbours by $\lfloor \sqrt{n'} \rfloor = 8$, so that $R(V) \ge 16 + 8 = 24$ and $S \ge 24 - 12 = 12$ and hence the solution cannot be optimal. Thus, in an optimal solution, all parts that touch three borders
must also include the two corresponding corners.

If a part $V$ has $T(V) = 4$, it must include at least one corner, because otherwise the four corner points are in different parts separated by $V$, and hence we have at least five parts, which is a contradiction. If $V$ does not contain another corner, the three remaining corners are in different parts and we can count 8 neighbours for each remaining corner (in the same way as for the case $T(V) = 3$ above), giving $R(V) \ge 24$ and $S \ge 12$. Thus, in an optimal solution, all parts that touch four borders must include at least two corners.

In summary, we know that in an optimal solution all four parts include at least one corner, which implies that they all include exactly one corner. Thus, a part cannot touch three or four borders, as it would then have to include at least two corners. Therefore, each part $V$ has $T(V) = 2$ and includes one corner.

The final argument for the optimality of the cost of $C = 57$ is obtained by repeatedly applying Lemma 3.2. The centre points of the mesh are the points $(7, 7)$, $(8, 7)$, $(7, 8)$, $(8, 8)$. If $V$ contains $(7, 7)$, it has $R(V) \ge 16$ by Lemma 3.2. The same bound also holds for the other centre points, as can be seen by applying the lemma to a rotated mesh. This implies that each part owning a centre point has a surplus of at least 4. As a consequence, at most two parts can contain a centre point in an optimal solution. This implies that there is a part $V$ with at least two centre points, and again by the same lemma, $R(V) \ge 17$.

Assume wlog that $V$ is a part with two centre points, and that the corner of $V$ is $(0, 0)$. If there is another part $V' \neq V$ that has a centre point, we have $R(V') \ge 16$ and hence $S \ge 17+16-24 = 9$ and $C \ge 57$. Therefore, this solution cannot be better than the optimal solution given by Figure 17. (Actually, this situation occurs in the optimal solution of the figure.) If there is no such part $V'$, then $V$ must contain all centre points, and hence applying Lemma 3.2 for the point $(8, 8)$ gives $R(V) \ge 18$ and $S \ge 6$. In the following, we will show that then other points beyond the four centre points must be included as well in this set $V$, if we want to achieve a better solution, with cost $C < 57$ and surplus $S \le 8$. In our argument, we will only look at points on the three diagonals $i = j - 1$, $i = j$, and $i = j + 1$. We will consider the points closest to the centre in turn.

Let $V$ be the part that contains the four centre points and the corner point $(0, 0)$, and let $V' \neq V$ be the part that contains the top-right corner point $(15, 15)$. Note that $R(V) \ge 18$. The other two parts cannot hold points from the three mentioned diagonals, because the distance to their corners is too large, resulting in $R \ge 16$ by Lemma 3.2. This would give a total surplus of $18 + 16 - 24 = 10$, which is too large. Figure 18 illustrates the situation.

For a point $(i, j) \in V'$, the distance to the top-right corner point $(15, 15)$ should be considered when applying Lemma 3.2. This gives a bound

$$R(V') \ge (15 - i) + (15 - j) + 2 = 32 - i - j. \quad (14)$$

This bound implies that points $(i, j)$ with $i + j \le 16$ cannot be in $V'$, because the surplus would then be at least 10. Therefore, all the points of the central diagonals that are to the left and below the centre must be in $V$.

If $(9, 8) \in V'$, then $R(V') \ge 15$ by Eqn (14). This gives a total surplus $S \ge 18 + 15 - 24 = 9$, so this solution cannot be better than the optimal solution given by Figure 17. Thus, $(9, 8) \in V$, and similarly $(8, 9) \in V$. By Lemma 3.2, we now have $R(V) \ge 19$.

If $(9, 9) \in V'$, then $R(V') \ge 14$ by Eqn (14). This gives a total surplus $S \ge 19 + 14 - 24 = 9$, so this solution cannot be better. Thus, $(9, 9) \in V$ and by Lemma 3.2, we now have $R(V) \ge 20$.

If $(10, 9) \in V'$, then $R(V') \ge 13$ by Eqn (14). This gives a total surplus $S \ge 20 + 13 - 24 = 9$, so this solution cannot be better. On the other hand, if $(10, 9) \in V$ then $R(V) \ge 21$ by Lemma 3.2. This gives a total surplus $S \ge 21 - 12 = 9$, so this solution also cannot be better. Hence, we conclude that the solution with cost $C = 57$ given by Figure 17 cannot be improved.
<figure><img src="image_23.png" /><figcaption>Figure 18: Three central diagonals of a 16 × 16 mesh with a solution assumed to be better than that of Figure 17. The solution assigns the four centre points and point (0,0) to part V (shown by red closed disks) and point (15, 15) to part V' (shown by yellow closed disks). The centre of the mesh is marked by red dashed lines. Points outside the three diagonals are not shown. The assignment of point (10,9) (or (9,10)) then leads to a contradiction.</figcaption></figure>

## 4.2 Developing heuristics

### 4.2.1 Purely combinatorial approach

A purely combinatorial approach using breadth-first search (BFS) was investigated by George and Liu [10] for various partitioning problems on graphs. One approach specifically developed for the problem at hand was described by Uçar and Çatalyürek [18] and further elaborated upon by Grandjean and Uçar [13]. This specific approach is based on a special BFS starting from a given point while strictly following the mesh structure in visiting the neighbours of a point. This enables applying the same method to any size of mesh and any number of parts. We summarize this approach for our particular case of partitioning an $I × I$ mesh into four parts, where we assume that $I$ is even.

For finding the top-left part, the BFS-based approach starts with putting the point (0, $I-1$) into a queue, assigning it to the part, and appending first the downwards neighbour of (0, $I-1$), and then its right neighbour at the end of the queue. The approach then repeatedly removes a point from the front of the queue, assigns it to the current part, as long as a total of $I^2/4$ points has not been reached, and then appends its downward and right neighbours at the end of the queue. The bottom-right part is a mirror image of the top-left one along the diagonal—this is a slight modification of the original method from Grandjean and Uçar; in the original one the last wavefronts were filled in the reverse order for the two triangular parts. Observe that these two parts are triangular-shaped as in Section 3.1. Then, the top-right part is found by starting a BFS from the point ($I-1, I-1$) and visiting neighbours to the left and then downwards, as long as they are not assigned to the two triangular parts found so far. Obviously, the points that remain after these three parts have been found form the fourth part. That part can also be found by starting a BFS from the point (0,0) and visiting the neighbours of a point in the order first upwards and then to the right.
### 4.2.2 Heuristics for ILP solvers

We next formulate the partitioning problem as an Integer Linear Program (ILP), and add additional constraints that are inspired by the presented theoretical analysis. Some of these constraints heuristically reduce the solution space.

The decision variables are:

* $x_{ij}^{(t)}$ for $i, j = 0, \dots, I-1$, and $t = 0, 1, 2, 3$, which will be used to assign the points to the four parts.

* $n_{ij}^{(t)}$ for $i, j = 0, \dots, I-1$, and $t = 0, 1, 2, 3$, which will model the connectedness of a point $(i, j)$ to a part $t$.

In order to simplify notation for the ILP, we will use $ij$ to refer to a point, and $P$ to refer to the set of all points. A summation of the form $\sum_{ij \in P} x_{ij}^{(t)}$ runs over all points and sums $x_{ij}^{(t)}$. Let $N_{ij}$ be the set of neighbours of the point $ij$. With these definitions, the ILP for 4-way mesh partitioning reads as

$$
\begin{array}{ll}
\text{minimise} & \displaystyle\sum_{ij \in P} \left(-1 + \sum_{t=0}^{3} n_{ij}^{(t)}\right) \\
\text{subject to} & \displaystyle\sum_{t=0}^{3} x_{ij}^{(t)} = 1 \quad \text{for all } ij \in P \\
& \displaystyle\sum_{ij \in P} x_{ij}^{(t)} = I^2/4 \quad \text{for } t = 0, 1, 2, 3 \qquad \text{(BasicILP)} \\
& n_{ij}^{(t)} \ge x_{pq}^{(t)} \quad \text{for all } ij \in P, pq \in \{ij\} \cup N_{ij}, \text{ and} \\
& \phantom{n_{ij}^{(t)} \ge} t = 0, 1, 2, 3 \\
& x_{00}^{(0)} = 1 \\
& x_{ij}^{(t)}, n_{ij}^{(t)} \in \{0, 1\} \quad \text{for all } ij \in P, \text{ and all } t = 0, 1, 2, 3,
\end{array}
$$

where the first and the second constraints ensure assigning each point to a part and having a perfect balance among the parts. The third constraint states that a point $ij$ is connected to a part $t$, if either $ij$ or at least one of its neighbours is assigned to the same part $t$. The fourth constraint fixes wlog the part containing the point $(0,0)$ as the part $t=0$. With all variables being binary, the objective function thus counts for each $ij \in P$ to how many parts $ij$ should be sent from its home part designated by the unique nonzero variable $x_{ij}^{(t)}$ for $t=0, 1, 2, 3$. We do not impose constraints for the connectivity of the parts in the ILP formulation BasicILP above.

Next, based on the analysis in Section 4.1, we add additional constraints to BasicILP for obtaining stronger formulations. We first preassign each corner to a unique part, so that we obtain the formulation:

BasicILP and the following additional constraints

$$
\begin{array}{l}
x_{0,I-1}^{(1)} = 1 \\
x_{I-1,0}^{(2)} = 1 \\
x_{I-1,I-1}^{(3)} = 1.
\end{array}
\qquad \text{(ILPCor)}
$$

Note that while assigning each corner to a unique part makes sense, the proof that there is an optimal solution with this property from Section 4.1 is for the 16 × 16 mesh only.

We then deal with the four centre points, as also shown in Section 4.1, where we assign the two centre points on the diagonal $(0,0)$-to-$(I-1, I-1)$ to the parts holding the respective corners.
We also forbid the assignment of the remaining two centre points to the other two parts. This leads to the formulation:

ILPCor and the following additional constraints

$$ 
\begin{align*}
x_{I/2-1, I/2-1}^{(0)} &= 1 \\
x_{I/2, I/2}^{(3)} &= 1 \tag*{(ILPCorCen)} \\
x_{I/2-1, I/2}^{(1)} &= x_{I/2-1, I/2}^{(2)} = 0 \\
x_{I/2, I/2-1}^{(1)} &= x_{I/2, I/2-1}^{(2)} = 0.
\end{align*}
$$

We then add another set of constraints by using Lemma 3.2 and the lower bound from Lemma 3.3 to forbid certain assignments. For a given $I$, let $k$ be such that $\phi_2(k) < I^2/4 \le \phi_2(k+1)$ so that by Lemma 3.3, we have $k+3$ as a lower bound for a part. Let $C$ be an upper bound on the total communication volume, computed by a heuristic solution for example. Then assigning a point $(i, j)$ to part $t=0$ results in a total communication volume of at least $i+j+2+3(k+3)$, where we assume that all parts touch exactly two borders. If this value is larger than $C$, we can forbid the assignment of $(i, j)$ to $t=0$. For each point $(i, j)$ and part $t$ having a unique corner point, we compute these values, and when the condition is fulfilled we add a constraint of the form $x_{ij}^{(t)} = 0$ to the ILP. This leads to the following formulation

$$ 
\begin{align*}
\text{ILPCorCen} \text{ and the following additional constraints} \\
x_{ij}^{(t)} &= 0 \text{ if assigning } (i, j) \text{ to } t \text{ results in a} \tag*{(ILPCorCenForb)} \\
\text{total communication volume larger than } C.
\end{align*}
$$

### 4.2.3 Hybrid heuristic

We can combine both approaches. We start with the combinatorial algorithm to obtain a solution. Then we identify the set $C$ of points that need to be communicated. We use the formulation ILP-CorCenForb and additional constraints to fix the assignment of all points in $P \setminus C$ as computed by the combinatorial algorithm. The variables corresponding to the points in $C$ are left as free. We then run an ILP solver on this constrained formulation of ILPCorCenForb. We call the resulting heuristic method rbFast.

## 5 Computational results

We present experimental results obtained by running the Gurobi solver [14] version 11.0.3 on the ILP formulation of the problem, with and without constraints suggested by the theory. This solver makes use of the available CPUs of the running machine in an automatic setting by default. The machine used for the experiments has two Intel(R) Xeon(R) Gold 6242R CPU @ 3.10GHz, with a total of 40 physical cores on which up to 32 threads were used by Gurobi. This machine has 377GB of memory.

Gurobi reports the following performance metrics: wall clock time for solution, the total number of simplex iterations, the number of branch-and-bound nodes (BB-nodes) explored, and a metric called work units. We report all these four metrics in the tables below. We note that the experiments were not run in an exclusive mode, and hence the run time should be taken with a grain of salt. According to the Gurobi documentation, one work unit corresponds roughly to one second on a single thread, but greatly depending on the hardware used and the ILP being solved. The work unit metric is deterministic and hence can be reproduced in subsequent runs of the same ILP on the same machine. All metrics combined allow a fair comparison in general. In
<table><caption>Table 1: Gurobi's performance for solving various ILPs for the 16 × 16 mesh, whose optimal values are all 57.</caption><thead><tr><th>ILP</th><th>Work Units</th><th>Simplex Iterations</th><th>BB-nodes</th><th>Time (s)</th></tr></thead><tbody><tr><td>BasicILP</td><td>1 466 702.21</td><td>35 095 531 028</td><td>93 218 994</td><td>761 276.40</td></tr><tr><td>ILPCor</td><td>432 095.37</td><td>10 591 820 945</td><td>26 888 845</td><td>357 092.87</td></tr><tr><td>ILPCorCen</td><td>23 127.76</td><td>719 550 800</td><td>1 376 662</td><td>8 368.37</td></tr><tr><td>ILPCorCenForb</td><td>16.93</td><td>348 684</td><td>1 246</td><td>27.71</td></tr></tbody></table>

<table><caption>Table 2: Gurobi's performance for solving the ILP formulation ILPCorCenForb for the 32 × 32 mesh, whose optimal value is 113.</caption><thead><tr><th>Work Units</th><th>Simplex Iterations</th><th>BB-nodes</th><th>Time (s)</th></tr></thead><tbody><tr><td>1 400 833.97</td><td>15 745 993 469</td><td>8 937 468</td><td>1 211 916.16</td></tr></tbody></table>

In our case, we expect the strongest formulation ILPCorCenForb to deliver exponential reductions with respect to BasicILP in the number of BB-nodes. Exponential reductions in this metric should result in exponential reductions in the other three metrics.

One can give Gurobi an initial solution to accelerate the computation. We initialized Gurobi by the output from rbFast. We set the Gurobi parameters “symmetry = 2”, “MIPFocus = 3”, “Cuts = 3”, and “OBBT = 3”, so that it aggressively tries to prove the optimality of the current solution.

Table 1 displays Gurobi's performance metrics for the 16 × 16 mesh. All ILP formulations obtain 57 as the optimal objective value. As seen in this table, solving the formulation BasicILP took 761 276.40 seconds, which is nearly nine days. The run time and all other metrics reduce tangibly with the formulation ILPCor. An order of magnitude reduction comes with using the formulation ILPCorCen. The last formulation ILPCorCenForb reduces all metrics by another three orders of magnitude and the run time is only 27.71 seconds. The initial solution given is connected as shown in Figure 17. Confirming with Gurobi that the initial solution is also optimal for the four ILPs strongly suggests that there are always optimal solutions which have connected parts for the mesh partitioning problem.

We also report that an ILP formulation in which ILPCor is enriched with the constraints forbidding certain assignments was also very successful, although not as much as ILPCorCenForb. This formulation on the 16 × 16 mesh had 407.16 work units and 10 344 356 simplex iterations, explored 27 926 BB-nodes, and took 198.35 seconds. We also note that one can forbid assignment of a pair of points to a given part if doing so results in too many receives per part to be optimal. We had enriched BasicILP with these constraints, but Gurobi's performance was worse than that for ILPCor. We conclude that the combination of assigning four corners and using these assignments to restrict certain other assignments is the most effective approach.

Encouraged by the performance of Gurobi in solving ILPCorCenForb for the 16 × 16 mesh, we tried it on larger meshes. We have statistics for the 32 × 32 mesh shown in Table 2, whose optimal objective value (communication cost) is 113. As seen from this table, it took around two weeks to solve ILPCorCenForb. We had tried running Gurobi to solve BasicILP for the same mesh, but it reported a memory error before exploring any BB-nodes. We note that the number of simplex iterations, BB-nodes explored, and work units are less than those of BasicILP for the 16 × 16 mesh, highlighting the advantages of the proposed strongest ILP formulation once more.

We next turn our attention to the proposed hybrid solver rbFast. Table 3 compares the communication volume obtained by our rbFast method with those obtained by three hypergraph
<table><caption>Table 3: The volume of communication obtained by different partitioning methods on $I \times I$ meshes. PaToH is run with the quality setting; KaHyPar-r follows the recursive bisection paradigm, KaHyPar-k is a direct k-way partitioning method. PaToH and KaHyPar variants have an imbalance parameter of 0.01. The minimum of five runs is reported for PaToH and KaHyPar variants. Previous best is from Grandjean and Uçar, slightly modified to have mirror symmetry for the triangular parts. The smallest volume for each mesh is marked with bold. The results with * are confirmed to be optimal for BasicILP theoretically in Section 4.1 as well as by the ILP solver. The result marked by ** is shown to be optimal for ILPCorCenForb and hence for ILPCorCen by the ILP solver.</caption><thead><tr><th>I</th><th>PaToH</th><th>KaHyPar-r</th><th>KaHyPar-k</th><th>Previous best</th><th>rbFast</th></tr></thead><tbody><tr><td>16</td><td>60</td><td>62</td><td>62</td><td>*57</td><td>*57</td></tr><tr><td>32</td><td>118</td><td>123</td><td>118</td><td>116</td><td>**113</td></tr><tr><td>64</td><td>242</td><td>241</td><td>236</td><td>222</td><td>221</td></tr><tr><td>128</td><td>477</td><td>491</td><td>462</td><td>444</td><td>441</td></tr><tr><td>256</td><td>975</td><td>982</td><td>936</td><td>878</td><td>877</td></tr><tr><td>512</td><td>1970</td><td>2001</td><td>1859</td><td>1752</td><td>1751</td></tr><tr><td>1024</td><td>3969</td><td>3986</td><td>3736</td><td>3500</td><td>3499</td></tr></tbody></table>

partitioners: PaToH [8] with its quality setting; KaHyPar with recursive bisection (KaHyPar-r) and with direct k-way partitioning (KaHyPar-k) [12, 17]. The table also includes the best known results before our work; these numbers were obtained with the modified combinatorial solver of Grandjean and Uçar [13]. As seen in this table, rbFast obtains the smallest communication volume for all mesh sizes. The general hypergraph partitioners have larger communication volume, and they do not in general have the perfect load balance. The difference between the previous best and rbFast is at most 3, which confirms the effectiveness of both approaches. The results by rbFast stand as the current best. Since its cost for the 16 × 16 mesh is provably optimal, and its cost for the 32 × 32 mesh is optimal for a restrictive ILP formulation, we conjecture that rbFast obtains optimal results also in other cases.

In Table 4, we give Gurobi's performance in solving the ILPs of rbFast for the meshes from Table 3. Gurobi again uses up to 32 threads in solving the ILPs here. Recall that rbFast calls Gurobi after an initial solution computed by the combinatorial solver. The time reported in Table 4 is only for Gurobi; the run time complexity of the combinatorial solver is linear and hence the run time reported in the table is the most significant part. We first observe that Gurobi explores only a single BB-node. This happens because the root relaxation of Gurobi obtains results that are very close to that of the initial solution. We next observe that Gurobi spends more work units for $I = 128$ than it spends for $I = 256$. This is probably due to the fact that the difference between the initial solution and the optimal one for $I = 128$ is larger than that for $I = 256$, requiring more work. We do not compare the run time of rbFast with that of the hypergraph partitioning tools, as they are much more general, applicable, and solve a related problem only (with imperfect balance). For completeness, we note that KaHyPar-k, KaHyPar-r, and PaToH took 190.4, 129.3, and 9.8 seconds, respectively, in 4-way partitioning the hypergraph corresponding to the 1024 × 1024 mesh.

# 6 Concluding remarks

We have studied the problem of partitioning a regular rectangular mesh into equal-sized connected parts for the purpose of parallel 5-point stencil computations, where the objective is to
<table><caption>Table 4: Gurobi's performance in solving the ILPs of the proposed rbFast method for $I \times I$ meshes.</caption><thead><tr><th>I</th><th>Work Units</th><th>Simplex Iterations</th><th>BB-nodes</th><th>Time (s)</th></tr></thead><tbody><tr><td>16</td><td>0.01</td><td>369</td><td>1</td><td>0.03</td></tr><tr><td>32</td><td>0.17</td><td>1564</td><td>1</td><td>0.36</td></tr><tr><td>64</td><td>0.30</td><td>2525</td><td>1</td><td>0.86</td></tr><tr><td>128</td><td>1.66</td><td>4299</td><td>1</td><td>3.97</td></tr><tr><td>256</td><td>1.54</td><td>6756</td><td>1</td><td>5.18</td></tr><tr><td>512</td><td>6.37</td><td>14353</td><td>1</td><td>7.02</td></tr><tr><td>1024</td><td>24.15</td><td>27232</td><td>1</td><td>64.67</td></tr></tbody></table>

minimise the total communication volume. We have first systematically derived isoperimetric inequalities that provide lower bounds on the number of neighbouring points of a part when the part touches zero, one, two, three, or four borders. To the best of our knowledge, the derived isoperimetric inequalities for the cases of a part touching one, three, and four borders are novel, while those for the cases of a part touching zero or two borders are known. Our inequalities in all cases are proven with detailed arguments. We have then combined the results to present an optimal solution along with the proof of optimality for the 16 × 16 mesh problem with 4 parts, which was an open problem.

We have made use of the presented theoretical results in two practical contexts. First, we have added constraints heuristically to an integer linear programming formulation of the problem at hand and obtained an improvement of four orders of magnitude in the run time. Second, we have combined the enriched formulation with a combinatorial solver to propose a practical method to partition meshes. Experiments with this method in 4-way partitioning of meshes of size up to 1024×1024 show that it consistently obtains solutions with a smaller communication volume than the state-of-the-art hypergraph partitioners. For the 1024 × 1024 mesh, the improvements range from 6.3% to 12.2%. Furthermore, the proposed method is also faster than the best available tool for partitioning this mesh, while achieving a 6.3% quality improvement over it.

We are confident that some of the solutions obtained by the proposed partitioning method (see Table 3) are optimal or very close to optimal. We leave it as an open problem to show if any of them are optimal. Our methodology in Section 4.1 where we showed the optimal partitioning of the 16 × 16 mesh is clearly a basis for generalisation but this would require possibly tedious adaptations for other mesh sizes. A rigorous, easy to follow recipe for that methodology, potentially based on computational tools rather than a full analytical result, will certainly be of value.

## Acknowledgment

This work was supported in part within the framework of the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "France 2030" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Further support was provided by the Laboratoire de l'Informatique du Parallélisme (LIP) at the Ecole Normale Supérieure de Lyon, and by a Guest Research Fellowship at the Collegium – Institut d'études avancées de Lyon.
References

[1] S. ACER, E. G. BOMAN, C. A. GLUSA, AND S. RAJAMANICKAM, *Sphynx: A parallel multi-GPU graph partitioner for distributed-memory systems*, Parallel Computing, 106 (2021), p. 102769.

[2] D. AJWANI, R. H. BISSELING, K. CASEL, Ü. V. ÇATALYÜREK, C. CHEVALIER, F. CHUDIGIEWITSCH, M. F. FARAJ, M. R. FELLOWS, L. GOTTESBÜREN, T. HEUER, G. KARYPIS, K. KAYA, J. LACKI, J. LANGGUTH, X. S. LI, R. MAYER, J. MEINTRUP, Y. MIZUTANI, F. PELLEGRINI, F. PETRINI, F. A. ROSAMOND, I. SAFRO, S. SCHLAG, C. SCHULZ, R. SHARMA, D. STRASH, B. D. SULLIVAN, B. UÇAR, AND A. YZELMAN, *Open problems in (hyper)graph decomposition*, CoRR, abs/2310.11812 (2023), https://doi.org/10.48550/ARXIV.2310.11812.

[3] G. BAREQUET AND G. BEN-SHACHAR, *Minimum-perimeter lattice animals and the constant-isomer conjecture*, The Electronic Journal of Combinatorics, 29 (2022), p. P3.45.

[4] G. BAREQUET AND G. BEN-SHACHAR, *Algorithms for counting minimum-perimeter lattice animals*, Algorithmica, 85 (2023), pp. 75–99.

[5] R. H. BISSELING, *Parallel Scientific Computation: A Structured Approach using BSP*, Oxford University Press, Oxford, UK, second ed., 2020.

[6] R. H. BISSELING AND W. F. McCOLL, *Scientific computing on bulk synchronous parallel architectures*, in Technology and Foundations: Information Processing '94, Vol. I, B. Pehrson and I. Simon, eds., vol. 51 of IFIP Transactions A, Amsterdam, 1994, Elsevier Science Publishers, pp. 509–514.

[7] B. BOLLOBÁS AND I. LEADER, *Compressions and isoperimetric inequalities*, Journal of Combinatorial Theory, Series A, 56 (1991), pp. 47–62, https://doi.org/10.1016/0097-3165(91)90021-8.

[8] Ü. V. ÇATALYÜREK AND C. AYKANAT, *PaToH: A multilevel hypergraph partitioning tool, version 3.3*, Bilkent University, Department of Computer Engineering, Ankara, Turkey, 1999.

[9] C. CHEVALIER, H. HIRTZ, F. LEDOUX, AND S. MORAIS, *Coupe: A mesh partitioning platform*, in SIAM International Meshing Roundtable 2023, E. Ruiz-Gironés, R. Sevilla, and D. Moxey, eds., Berlin, Heidelberg, 2024, Springer-Verlag, pp. 43–63.

[10] A. GEORGE AND J. W. H. LIU, *Computer Solution of Large Sparse Positive Definite Systems*, Prentice-Hall, Englewood Cliffs, N.J., 1981.

[11] J. R. GILBERT, G. L. MILLER, AND S.-H. TENG, *Geometric mesh partitioning: Implementation and experiments*, SIAM Journal on Scientific Computing, 19 (1998), pp. 2091–2110, https://doi.org/10.1137/S1064827594275339.

[12] L. GOTTESBÜREN, M. HAMANN, S. SCHLAG, AND D. WAGNER, *Advanced flow-based multilevel hypergraph partitioning*, in 18th International Symposium on Experimental Algorithms, Leibniz International Proceedings in Informatics, Dagstuhl, Germany, 2020, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 11:1–11:15.
[13] A. GRANDJEAN AND B. UÇAR, *On partitioning two dimensional finite difference meshes for distributed memory parallel computers*, in Proceedings of the 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, Los Alamitos, CA, USA, 2014, IEEE Computer Society, pp. 9–16.

[14] GYROBI OPTIMIZATION, LLC, *Gurobi Optimizer Reference Manual*, 2025, https://www.gurobi.com. Accessed March 24, 2025.

[15] F. KONG, R. H. STOGNER, D. R. GASTON, J. W. PETERSON, C. J. PERMANN, A. E. SLAUGHTER, AND R. C. MARTINEAU, *A general-purpose hierarchical mesh partitioning method with node balancing strategies for large-scale numerical simulations*, in 2018 IEEE/ACM 9th workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, Dallas, TX, USA, 2018, IEEE Computer Society, pp. 65–72.

[16] F. PELLEGRINI, *Scotch and PT-Scotch graph partitioning software: An overview*, in Combinatorial Scientific Computing, U. Naumann and O. Schenk, eds., Chapman and Hall/CRC, New York, 2012, pp. 373–406.

[17] S. SCHLAG, T. HEUER, L. GOTTESBÜREN, Y. AKHREMTSEV, C. SCHULZ, AND P. SANDERS, *High-quality hypergraph partitioning*, ACM Journal of Experimental Algorithms, 27 (2022), pp. 1–39, Article 1.9.

[18] B. UÇAR AND Ü. V. ÇATALYÜREK, *On the scalability of hypergraph models for sparse matrix partitioning*, in Proceedings of the 18th Euromicro Conference on Parallel, Distributed, and Network-based Processing, M. Danelutto, J. Bourgeois, and T. Gross, eds., Los Alamitos, CA, USA, 2010, IEEE Computer Society, pp. 593–600.

[19] D. VAINSENCHER AND A. M. BRUCKSTEIN, *On isoperimetrically optimal polyforms*, Theoretical Computer Science, 406 (2008), pp. 146–159.

[20] C. WALSHAW AND M. CROSS, *Mesh partitioning: A multilevel balancing and refinement algorithm*, SIAM Journal on Scientific Computing, 22 (2000), pp. 63–80, https://doi.org/10.1137/S1064827598337373.

[21] D.-L. WANG AND P. WANG, *Discrete isoperimetric problems*, SIAM Journal on Applied Mathematics, 32 (1977), pp. 860–870, https://doi.org/10.1137/0132073.
informatics mathematics
Inria

RESEARCH CENTRE
Centre Inria de Lyon

Bâtiment CEI-2, Campus La Doua
56, Boulevard Niels Bohr - CS 52132
69603 Villeurbanne

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399