Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a polygon $P$ on the plane, is there a rigorous method or algorithm to compute or approximate a linear transformation $T$ which maximizes the following ratio?

$$\frac{\mathrm{Area}[T(P)]}{\mathrm{Perimeter}[T(P)]^2}$$

share|improve this question
    
If you just project the polygon onto the $e_1$ axis, then you'll have a line (unless the original polygon was a single vertical line), which will have $>0$ "perimeter" and 0 area, so this ratio will be zero. –  andybenji Dec 19 '12 at 14:31
3  
@andybenji: that shows that the minimization leads to a trivial/degenerate solution. But here we are seeking the maximum (informally, we are trying to get as near to a circle as possible). –  leonbloy Dec 19 '12 at 14:40
add comment

2 Answers

up vote 11 down vote accepted
+100

This is not an answer, but may be a helpful reformulation. We can scale any linear transformation to make it have determinant 1 (so that it preserves area) without changing the isoperimetric ratio. This changes the problem to,

Given a polygon, what matrix $A$ in $SL_2(\mathbb{R})$ maximizes $\frac{1}{(Perimeter(A(P)))^2}$?

Clearly, this is the same as minimizing the perimeter. Also, we can regard each edge as a vector $a_i$. Since translation does not change the length distortion under $A$, your question reduces to,

Given a collection of $n$ 2-dimensional vectors $a_1,...,a_n$, what matrix $A$ in $SL_2(\mathbb{R})$ minimizes $\sum |Aa_i|$?

I don't know the answer to this question, either, but it seems like something that must have been studied before. Hopefully someone can finish this answer!

Edit: I realized that if you consider a 2x2 matrix as a function of four variables, you can solve this last reformukation using Lagrange multipliers (where the constraint is det A=1).

Edit: Because the perimeter and area are also invariant under rotation, we can choose a final rotation that simplifies the form of the matrix. For instance, we can force $(1,0)$ to be an eigenvector; this is equivalent to making the transformation matrix upper triangular. The additional constraint on the determinant leaves a two-parameter matrix: $$ A = \left( \begin{matrix}s & k \\ 0 & 1/s \end{matrix}\right). $$

share|improve this answer
    
I'm pretty sure that $|A a_i| = \sqrt{(s x_i + k y_i)^2 + (y_i/s)^2}$ is convex in $s$ and $k$, too. That makes this an unconstrained convex optimization problem, which is pretty nice. –  Rahul Dec 28 '12 at 8:16
add comment

Comment 1: In general, there is no closed form solution to find the linear transformation, you are seeking.

Comment 2: This is good news. You can reformulate your problem as a convex optimization problem and efficiently solve it using readily available convex packages.

SHORT ANSWER

Please refer to Brain Rushton's answer. Once you understand his explanation and reach at the end. It is very easy to solve it. This is the well-known unconstrained minimization of sum of norms. This can be converted into a second order cone program (SOCP). \begin{align} \min_{t_i,z}&\sum_{i=1}^{n}t_i \\ subject~to~&\lvert\lvert F_iz\rvert\rvert \leq t_i,~~\forall i=1,2,\dots,n \end{align} This can be efficiently solved using convex optimization packages like Stephen Boyd's CVX. Please read about minimization of sum of norms here (section 2.2)

LONG ANSWER

Here I will explain how to reach that formulation.

Notation: I assume the co-ordinates of the polygon are given and they are $z_1$,$z_2$,...,$z_n$. The co-ordinates are counted in one direction (clockwise or anticlockwise). So $z_1$ is adjacent to $z_2$, $z_2$ to $z_3$,.... and finally $z_n$ to $z_1$. Also $T$ denote the transformation. After applying this transformation, let $a_i=Tz_i, \forall i$. Note that all this vectors are $2 \times 1 $ and $T$ is $2 \times 2$. Thus

SKETCH OF APPROACH

step 1: Here I will prove that the problem is independent of area. It is solely dependent only on perimeter.

step 2: The problem can be converted as a convex problem.

STEP 1

Define $n$ matrices $A_i$ which are $2 \times 2$ as \begin{align} A_1=[z_1,z_2] \\ A_2=[z_2,z_3] \\ A_3=[z_3,z_4] \\ \dots \\ \dots \\ A_n=[z_n,z_1] \end{align} Then the area of the polygon before transformation is given by \begin{align} P=(1/2)*(~\det(A_1)+\det(A_2)+\dots+\det(A_N)~) \end{align} It is easy to see that the area after transformation is given by \begin{align} Q &=(1/2)*(~\det(TA_1)+\det(TA_2)+\dots+\det(TA_N)~) \\ &=(1/2)*(\det(T))*(~\det(TA_1)+\det(TA_2)+\dots+\det(TA_N)~) \\ &=\det(T)P \end{align} where I used the fact $\det(AB)=\det(A)\det(B)$. Thus the area of the polygon just gets multiplied by the determinant of the linear transformation. As user Brian Rushton has pointed out in another answer. There is no less of generality, if you take this determinant as one, as the ratio is always preserved. Thus following his arguments, we can say the optimization problem is nothing but to minimize the perimeter of the new linear transformation.

STEP 2

Thus the problem becomes \begin{align} \min_{T\in \mathbb{R}^{2\times 2}}\mathrm{Perimeter}[T(P)] \end{align} Perimeter before transformation is given by \begin{align} Peri &=\lvert\lvert z_2-z_1\rvert\rvert+\lvert\lvert z_3-z_2\rvert\rvert \dots +\lvert\lvert z_n-z_1\rvert\rvert \\ &=\lvert\lvert d_1\rvert\rvert+\lvert\lvert d_2\rvert\rvert \dots +\lvert\lvert d_n\rvert\rvert \end{align} where $d_1=z_2-z_1$ and so on. After transformation, perimeter is given by \begin{align} T(Peri)&=\lvert\lvert Td_1\rvert\rvert+\lvert\lvert Td_2\rvert\rvert \dots +\lvert\lvert Td_n\rvert\rvert \end{align} Now comes the reformulation part. Define the $4 \times 1$ vector \begin{align} z=\begin{bmatrix}T_{11} \\ T_{12} \\T_{21} \\T_{22} \end{bmatrix} \end{align} where $T_{ij}$ is the $(i,j)$ entry of $T$. Then make the important observation \begin{align} \begin{bmatrix}T_{11} & T_{12} \\T_{21} & T_{22} \end{bmatrix}\begin{bmatrix}x \\ y\end{bmatrix}=\begin{bmatrix}x & y & 0 & 0 \\ 0 & 0 & x & y\end{bmatrix}\begin{bmatrix}T_{11} \\ T_{12} \\T_{21} \\T_{22} \end{bmatrix} \end{align} Thus, let $d_i=(x_i,y_i)$ for all $i$. Also, for all $i$ define $2\times 4$ matrix \begin{align} F_i=\begin{bmatrix}x_i & y_i & 0 & 0 \\ 0 & 0 & x_i & y_i\end{bmatrix} \end{align} Thus you have \begin{align} \lvert\lvert Td_i\rvert\rvert=\lvert\lvert F_iz\rvert\rvert \end{align} Substituting you have, \begin{align} \min_{T\in \mathbb{R}^{2\times 2}}\mathrm{Perimeter}[T(P)]~=~\min_{z\in \mathbb{R}^{4\times 1}} \lvert\lvert F_1z\rvert\rvert+\lvert\lvert F_2z\rvert\rvert \dots +\lvert\lvert F_nz\rvert\rvert \end{align} This is the well-known unconstrained minimization of sum of norms. This can be converted into a second order cone program (SOCP). Please read about minimization of sum of norms here (section 2.2) \begin{align} \min_{t_i,z}&\sum_{i=1}^{n}t_i \\ subject~to~&\lvert\lvert F_iz\rvert\rvert \leq t_i,~~\forall i=1,2,\dots,n \end{align} Essentially, you restrict each term $\lvert\lvert F_iz\rvert\rvert$ below $t_i$ and minimize the sum of all $t_i$. This is same as minimizing sum of $\lvert\lvert F_iz\rvert\rvert$

share|improve this answer
1  
Hmm, in step 2, where has the constraint $\det\,T=1$ gone? If $T$ is unconstrained, the global minimum obviously occurs at $T=0$. –  user1551 Dec 24 '12 at 12:19
    
In the "notation" section you denote by $a_i$ the transformed vertices, but below you change that meaning ($a_1 = z_2 - z_1$) –  leonbloy Dec 24 '12 at 18:52
    
@leonbloy Thanks, I corrected it. –  dineshdileep Dec 28 '12 at 6:37
    
@user1551 thanks a lot, give me sometime I will work on it. You have some idea to correct it? I suppose determinant is a non-convex quadratic criterion? is it? –  dineshdileep Dec 28 '12 at 6:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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