Dado un polígono $P$ en el avión, hay un riguroso método o algoritmo para calcular o aproximar una transformación lineal $T$, lo que maximiza la siguiente proporción?
$$\frac{\mathrm{Area}[T(P)]}{\mathrm{Perimeter}[T(P)]^2}$$
Respuestas
¿Demasiados anuncios?
Esta no es una respuesta, pero puede ser un útil reformulación. Podemos escalar cualquier transformación lineal para hacerlo tiene determinante 1 (por lo que se conserva de la zona) sin cambiar la isoperimétrico relación. Esto cambia el problema,
Dado un polígono, por lo que la matriz de $A$ $SL_2(\mathbb{R})$ maximiza $\frac{1}{(Perimeter(A(P)))^2}$?
Claramente, este es el mismo como minimizar el perímetro. También, podemos considerar cada borde como un vector $a_i$. Ya que la traducción no cambia la longitud de la distorsión en $A$, su pregunta se reduce a,
Dada una colección de $n$ 2 dimensiones de los vectores $a_1,...,a_n$, lo que la matriz de $A$ $SL_2(\mathbb{R})$ minimiza $\sum |Aa_i|$?
No sé la respuesta a esta pregunta, bien, pero parece como algo que debe haber sido estudiado antes. Esperemos que alguien pueda terminar esta respuesta!
Edit: me di cuenta de que si usted se considera una matriz de 2x2 como una función de cuatro variables, se puede resolver esta última reformukation el uso de multiplicadores de Lagrange (donde la restricción es det a=1).
Edit: Debido a que el perímetro y el área también son invariantes bajo de rotación, se puede elegir un final de la rotación que simplifica la forma de la matriz. Por ejemplo, podemos forzar a $(1,0)$ a ser un autovector; esto es equivalente a realizar la transformación de la matriz triangular superior. La restricción adicional en el determinante de las hojas de una de dos parámetros de la matriz: $$ A = \left( \begin{matrix}s & k \\ 0 & 1/s \end{de la matriz}\right). $$
dineshdileep
Puntos
3858
Comentario 1: En general, no es la forma cerrada de la solución para encontrar la transformación lineal, que usted está buscando.
Comentario 2: Esta es una buena noticia. Usted puede reformular el problema como un problema de optimización convexa y solucionar de manera eficiente es mediante fácilmente disponible convexa de los paquetes.
RESPUESTA CORTA
Por favor, consulte el Cerebro Rushton la respuesta. Una vez que usted entiende su explicación y llegar al final. Es muy fácil de resolver. Este es el conocido sin restricciones de la minimización de la suma de las normas. Este se puede convertir en un segundo orden de cono programa (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} Esto puede ser resuelto de manera eficiente el uso de optimización convexa paquetes como Stephen Boyd de la CVX. Por favor, lea acerca de la minimización de la suma de las normas aquí (sección 2.2)
RESPUESTA LARGA
Aquí voy a explicar cómo llegar a esa formulación.
Notación: asumo las coordenadas del polígono dado y que son $z_1$,$z_2$,...,$z_n$. Las coordenadas son de contado en una sola dirección (hacia la derecha o hacia la izquierda). Por lo $z_1$ es adyacente a $z_2$, $z_2$ a $z_3$,.... y, finalmente,$z_n$$z_1$. También se $T$ denotar la transformación. Después de la aplicación de esta transformación, vamos a $a_i=Tz_i, \forall i$. Tenga en cuenta que todo esto de los vectores de $2 \times 1 $$T$$2 \times 2$. Así
CROQUIS DE ENFOQUE
paso 1: Aquí voy a demostrar que el problema es independiente de la zona. Es el único que sólo depende de perímetro.
paso 2: El problema se puede convertir como un problema convexo.
PASO 1
Definir $n$ matrices $A_i$ se $2 \times 2$ \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} Entonces el área del polígono antes de la transformación está dada por \begin{align} P=(1/2)*(~\det(A_1)+\det(A_2)+\dots+\det(A_N)~) \end{align} Es fácil ver que la zona después de la transformación está dada por \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} donde he utilizado el hecho de $\det(AB)=\det(A)\det(B)$. Por lo tanto el área del polígono, simplemente se multiplica por el factor determinante de la transformación lineal. Como usuario de Brian Rushton ha señalado en otra respuesta. Hay no menos de generalidad, si usted toma este determinante como uno, como la relación siempre se conserva. Así, siguiendo sus argumentos, podemos decir que el problema de optimización es nada pero para minimizar el perímetro de la nueva transformación lineal.
PASO 2
Por tanto, el problema se convierte en \begin{align} \min_{T\in \mathbb{R}^{2\times 2}}\mathrm{Perimeter}[T(P)] \end{align} Perímetro antes de la transformación está dada por \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} donde $d_1=z_2-z_1$ y así sucesivamente. Después de la transformación, el perímetro está dada por \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} Ahora viene la reformulación parte. Definir el $4 \times 1$ vector \begin{align} z=\begin{bmatrix}T_{11} \\ T_{12} \\T_{21} \\T_{22} \end{bmatrix} \end{align} donde $T_{ij}$ $(i,j)$ entrada de $T$. A continuación, hacer una importante observación \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} Por lo tanto, vamos a $d_i=(x_i,y_i)$ todos los $i$. También, para todos los $i$ definir $2\times 4$ matriz \begin{align} F_i=\begin{bmatrix}x_i & y_i & 0 & 0 \\ 0 & 0 & x_i & y_i\end{bmatrix} \end{align} Por lo tanto usted tiene \begin{align} \lvert\lvert Td_i\rvert\rvert=\lvert\lvert F_iz\rvert\rvert \end{align} Sustituyendo se tiene, \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} Este es el conocido sin restricciones de la minimización de la suma de las normas. Este se puede convertir en un segundo orden de cono programa (SOCP). Por favor, lea acerca de la minimización de la suma de las normas aquí (sección 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} Esencialmente, restringir cada plazo $\lvert\lvert F_iz\rvert\rvert$ bajo $t_i$ y minimizar la suma de todos los $t_i$. Este es el mismo como la minimización de la suma de $\lvert\lvert F_iz\rvert\rvert$
