3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I can't figure out why consider an element of length $\sqrt{w^2+h^2}$ $\endgroup$ – the_candyman Aug 22 '14 at 8:03
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 22 '14 at 8:17
  • $\begingroup$ 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. $\endgroup$ – Greg Martin Aug 22 '14 at 8:19
  • 1
    $\begingroup$ 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 $\endgroup$ – the_candyman Aug 22 '14 at 8:31
  • $\begingroup$ Note that this is an isoperimetric problem on a graph ($mn$ vertices, with edges between all adjacent vertices) rather than the plane. $\endgroup$ – Semiclassical Aug 22 '14 at 13:29
1
$\begingroup$

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}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.