Maximum area / perimeter ratio

With no limitation, to achieve the maximum area with a fixed perimeter, the shape is a circle, and the area / perimeter ratio would be $\frac{L}{4\pi}$ where $L$ is the perimeter lenght.

However, if let's say the area is a grid with $m$ rows and $n$ columns, with each small rectangle horizontal side length $w$ and vertical side length $h$. And assume the perimenter shall be composed by segments of length $w$, $h$, or $\sqrt{w^2+h^2}$. Is there a way to determine the shape of maximum area/perimeter ratio?

• I can't figure out why consider an element of length $\sqrt{w^2+h^2}$ – the_candyman Aug 22 '14 at 8:03
• I assume the intention is to allow only segments that join a grid point to one of its eight direct neighbors, so that $\sqrt{w^2+h^2}$ is the length of the four possible diagonal segments. – Greg Martin Aug 22 '14 at 8:17
• To the OP: in the original problem, one could fix the perimeter or the area (to be any real number). But in the grid problem, the perimeter must be an integer linear combination of $w$, $h$, and $\sqrt{w^2+h^2}$, which in general is a pretty ugly-looking set. But the area is always an integer multiple of $\frac12wh$. So it probably makes more sense to fix the area and minimize the perimeter. – Greg Martin Aug 22 '14 at 8:19
• ok. It seems to be a combinatorics problem. Having fixed $m$, $n$, $w$ and $h$, find the shape on the grid such that the ratio is maximized – the_candyman Aug 22 '14 at 8:31
• Note that this is an isoperimetric problem on a graph ($mn$ vertices, with edges between all adjacent vertices) rather than the plane. – Semiclassical Aug 22 '14 at 13:29

I have managed to formulate the problem but I don't have a closed solution at this time. The idea is consider the first points coordinates to be $(0,0)$. Now, we shall represent our shape by the series $({a_1},{b_1}),...,({a_N},{b_N})$, where $$\begin{array}{l}{a_i} \in \left\{ { - 1,0,1} \right\}\\{b_i} \in \left\{ { - 1,0,1} \right\}\end{array}$$ The first constraint is that ${a_i}$ and ${b_i}$ could not both be zero at the same time so $$\left| {{a_i}} \right| + \left| {{b_i}} \right| \ge 1$$ The second and third constraints follow from the condition that the curve should be closed so that $$\begin{array}{l}\sum\limits_{i = 1}^N {{a_i}} = 0\\\sum\limits_{i = 1}^N {{b_i}} = 0\end{array}$$Up to here, we have formulated an $N$ point closed curve in the discrete space (with $N$ edges). The perimeter of this curve is equal to $${C_N} = \sum\limits_{i = 1}^N {\sqrt {{{({a_i}\delta x)}^2} + {{({b_i}\delta y)}^2}} }$$ where ${\delta x}$ and ${\delta y}$ represent the grid length in $x$ and $y$ directions. The surface of the curve could be found by partitioning the curve to triangles with the points $1$, $i$ and $i+1$ for $2 \le i \le N - 1$. This yields $${S_N} = \left| {\sum\limits_{i = 2}^{N - 1} {\frac{{{x_i}{y_{i + 1}} - {x_{i + 1}}{y_i}}}{2}} } \right|$$where ${{x_i}}$ and ${{y_i}}$ are the $x$ and $y$ coordinates of the $i$'th point. We have $$\begin{array}{l}{x_i} = \delta x\sum\limits_{j = 1}^{i - 1} {{a_j}} \\{y_i} = \delta y\sum\limits_{j = 1}^{i - 1} {{b_j}} \end{array}$$so by replacement and simplification, one may find $${S_N} = \frac{{\delta x\delta y}}{2}\left| {\sum\limits_{i = 1}^{N - 2} {\sum\limits_{j = 1}^{i - 1} {\left( {{a_j}{b_{i + 1}} - {a_{i + 1}}{b_j}} \right)} } } \right|$$Summarizing, the problem is finding $\left\{ {{a_i}} \right\}_{i = 1}^N$ and $\left\{ {{b_i}} \right\}_{i = 1}^N$ such that the functional $${F_N} = \frac{{{S_N}}}{{{C_N}}} = \frac{{\delta x\delta y\left| {\sum\limits_{i = 1}^{N - 2} {\sum\limits_{j = 1}^{i - 1} {\left( {{a_j}{b_{i + 1}} - {a_{i + 1}}{b_j}} \right)} } } \right|}}{{2\sum\limits_{i = 1}^N {\sqrt {{{({a_i}\delta x)}^2} + {{({b_i}\delta y)}^2}} } }}$$ is maximized subject to the conditions ${a_i} \in \left\{ { - 1,0,1} \right\}$, ${b_i} \in \left\{ { - 1,0,1} \right\}$, $\sum\limits_{i = 1}^N {{a_i}} = 0$, $\sum\limits_{i = 1}^N {{b_i}} = 0$, $\left| {{a_i}} \right| + \left| {{b_i}} \right| \ge 1$. A brute force approach to solving this problem is minimizing $$F = \frac{{2\sum\limits_{i = 1}^N {\sqrt {{{({a_i}\delta x)}^2} + {{({b_i}\delta y)}^2}} } }}{{\delta x\delta y\left| {\sum\limits_{i = 1}^{N - 2} {\sum\limits_{j = 1}^{i - 1} {\left( {{a_j}{b_{i + 1}} - {a_{i + 1}}{b_j}} \right)} } } \right|}} + {\left( {\sum\limits_{i = 1}^N {{a_i}} } \right)^2} + {\left( {\sum\limits_{i = 1}^N {{b_i}} } \right)^2} + \sum\limits_{i = 1}^N {\delta \left[ {\left| {{a_i}} \right| + \left| {{b_i}} \right|} \right]}$$where $\delta [m] = \left\{ \begin{array}{l}1,m = 0\\0,{\rm{O}}{\rm{.W}}{\rm{.}}\end{array} \right.$ is the Kronecker's delta in the ${3^{2N}}$ space of ${\left\{ { - 1,0,1} \right\}^{2N}}$.