¿Cómo encontrar el rectángulo de área máxima dentro de un polígono convexo?

21

En esta publicación estamos buscando algoritmos / ideas sobre cómo encontrar maximum-area-rectangle dentro de un polígono convexo .

En la siguiente figura, los números son las áreas de los rectángulos ajustados. Como se muestra, un rectángulo deseado puede variar en cada dimensión y puede estar en cualquier ángulo.

Editar:

  

No tenemos una idea clara de cómo abordar el problema mencionado como   así que preguntamos aquí. Sin embargo, adivinamos el rectángulo de área máxima   puede ser uno de los que tiene un borde alineado en (no necesariamente el   borde de la misma longitud, por supuesto) un borde del polígono.

    
pregunta Developer 26.04.2013 - 15:32

3 respuestas

4

Algunas notas demasiado grandes para poner en un comentario (aunque esto no sugiere un algoritmo obvio):

La línea de perforación (EDITADA) : al menos dos vértices del rectángulo del área máxima deben estar en el límite del polígono (es decir, a lo largo de un borde o en un vértice). Y si el rectángulo del área máxima no es un cuadrado, entonces al menos tres vértices deben estar en el límite del polígono.

Lo probé en cuatro pasos:

Nota # 1 : al menos un vértice del rectángulo del área máxima siempre estará en el límite del polígono. Esto es bastante obvio, pero una prueba podría ser la siguiente (por contradicción): suponga que tiene un rectángulo "máximo" sin vértice en el límite del polígono. Eso significa que habría al menos una pequeña habitación alrededor de cada uno de sus vértices. Así que puedes expandir un poco tu rectángulo, contradiciendo su maximalidad.

Nota # 2 : al menos dos vértices del rectángulo del área máxima siempre estarán en el límite del polígono. Una prueba podría ser así (nuevamente por contradicción): suponga que tiene un rectángulo "máximo" con un solo vértice en el límite (garantizado por la Nota # 1). Considere los dos bordes no adyacentes a ese vértice. Dado que sus puntos finales NO están en el límite, hay un pequeño espacio alrededor de cada uno. Así que cualquiera de esos bordes podría ser "extruido" un poco, expandiendo el área del polígono y contradiciendo su maximalidad.

Nota # 3 : Hay dos vértices diagonalmente opuestos del rectángulo del área máxima que se encuentran en el límite del polígono. (Sabemos por la Nota # 2 que hay al menos dos, pero no necesariamente que están uno frente al otro). Pero nuevamente, por contradicción, si los dos únicos vértices de borde eran adyacentes, entonces el borde opuesto (ninguno de cuyos vértices están en el límite) podrían extruirse un poco, aumentando el área del rectángulo y contradiciendo su maximalidad.

Nota # 4 : (EDITADO) Si el rectángulo del área máxima no es un cuadrado, tres de sus vértices se ubicarán en el límite del polígono.

Para demostrarlo, supongamos que no es así, es decir, que el rectángulo del área máxima no es un cuadrado, pero solo dos de sus vértices están en el límite del polígono. Mostraré cómo construir un rectángulo más grande, en contradicción con la máxima.

Llama a los vértices del rectángulo A , B , C y D . Sin pérdida de generalidad, suponga que B y D son los dos que están en el límite del polígono. Como A y C están en el interior del polígono, hay un margen de maniobra alrededor de ellos (representados con círculos alrededor de A y C en la imagen de abajo). Ahora dibuje un círculo alrededor del rectángulo, y deslice los puntos A y C un poco alrededor del círculo en la misma cantidad (para hacer A' y C' , ilustrados abajo) para que el nuevo rectángulo A'BC'D Es más cuadrado que el rectángulo original. Este proceso crea un nuevo rectángulo que también se encuentra dentro del polígono original y tiene un área más grande. Esto es una contradicción, así que la prueba está hecha.

Paracreerenesaprueba,debeconvencersedequeeláreadeunrectánguloinscritoenuncírculoaumentaamedidaquesevuelve"más cuadrada" (es decir, la diferencia entre las longitudes de los bordes se hace más pequeña). También necesita que el polígono sea convexo para que las nuevas líneas estén dentro de él. Y probablemente hay otros pequeños detalles que son barridos debajo de la alfombra, pero estoy bastante seguro de que todos funcionan.

    
respondido por el csd 03.10.2013 - 16:03
3

He hecho un boceto muy rápido y horrible sobre tu nota verde en la pregunta. No pude publicarlo como comentario, así que tuve que escribir una respuesta, incluso si no lo es.
Creo que en la imagen de abajo tenemos un rectángulo de área máxima (no perfecto, es solo un boceto hecho en Paint para dar una idea), y no creo que pueda encontrar uno más grande que tenga un lado común con el Bordes del plygon negro ...
Sin embargo, puedo estar equivocado, en ese caso, tengo todas mis disculpas.

    
respondido por el Saryk 03.10.2013 - 16:19
2

La mayoría de los otros algoritmos encuentran el área rectilínea del rectángulo máximo inscrita en un polígono convexo, y tienen una complejidad de O(log n) . No creo que supongas que el polígono de área máxima esté alineado con uno de los lados sea correcto, porque todo lo que deberías hacer es girar el polígono n veces, lo que resulta en una complejidad de O(n log n) , y en mi breve investigación no pude encontrar nada diciendo que fue tan fácil.

Sin embargo, el artículo Los rectángulos inscritos más grandes en polígonos convexos por Knauer, et. al., describe un algoritmo de aproximación que lo acercará a la respuesta correcta.

Como mejor entiendo el algoritmo, se basa en uno de los polígonos de área máxima alineados con ejes conocidos, y luego muestrea aleatoriamente puntos dentro del espacio de polones, genera múltiples ejes a partir de esas muestras aleatorias, itera sobre esos ejes y aplica el algoritmo alineado con el eje a cada uno, y luego devuelve el rectángulo más grande en ese conjunto.

    
respondido por el lreeder 30.09.2013 - 05:11

Lea otras preguntas en las etiquetas