We consider a problem in domain decomposition: assign jobs to parallel processors to minimize the total communication between jobs in different processors. This is the graph partition problem: assign nodes to sets so that the sets have equal size and the number of cut-arcs (arcs connecting nodes in different sets) is minimized. Nodes are jobs, sets are processors, and cut-arcs are interprocessor communication.

There has been much research on domain decomposition with squares, in which jobs may have to communicate with their north, south, east, or west neighbors. A polyomino is a finite edge-connected set of squares on a square grid. We can think of the jobs assigned to a processor as a polyomino, and interprocessor communication as boundary edges between polyominos. Yackel-Meyer-Christou proved that the min perimeter of a polyomino with area n is ceil(sqrt(4n)). So a lower bound for total interprocessor communication is the number of processors times the min perimeter of a subdomain (polyomino). Christou-Meyer proved by construction that this lower bound is asymptotically optimal; for large problems, there is a decomposition whose relative gap from the lower bound is close to 0.

We generalize this domain decomposition problem to triangles. A polyiamond is a finite edge-connected set of triangles on a triangular grid. We prove the following:

• The min perimeter of a polyiamond with area n is whichever of ceil(sqrt(6n)) + {0, 1} has the same parity as n.
• The max area of a polyiamond with perimeter p is round(p^2/6) - {0, 1}, where we choose 0 iff p = 0 mod 6.