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

Question

En esta publicación estamos buscando algoritmos / ideas sobre cómo encontrar el rectángulo con el área máxima dentro de un pólí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, por lo que preguntamos aquí. Sin embargo, suponemos que el rectángulo con el área máxima puede ser uno de aquellos que tiene un borde alineado en (no necesariamente la misma longitud de borde, por supuesto) un borde del pólígono.

Answer 1

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

La clave (EDITADO): Al menos dos vértices del rectángulo de á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 de área máxima no es un cuadrado, entonces al menos tres vértices deben estar en el límite del polígono.

Lo probé a mí mismo en cuatro pasos:

Nota #1: Al menos un vértice del rectángulo de área máxima siempre estará en el límite del polígono. Esto es bastante obvio, pero una demostración podría ser así (por contradicción): Supongamos que tuvieras un rectángulo "máximo" sin ningún vértice en el límite del polígono. Eso significa que habría un poco de espacio alrededor de cada uno de sus vértices. Así que podrías expandir tu rectángulo un poco, contradiciendo su máximo.

Nota #2: Al menos dos vértices del rectángulo de área máxima siempre estarán en el límite del polígono. Una demostración podría ser así (de nuevo por contradicción): Supongamos que tuvieras un rectángulo "máximo" con solo un vértice en el límite (garantizado por la Nota #1). Considera los dos bordes no adyacentes a ese vértice. Dado que sus extremos NO están en el límite, hay un poco de espacio alrededor de cada uno. Así que cualquiera de esos bordes podría ser "extraído" un poco, expandiendo el área del polígono y contradiciendo su máximalidad.

Nota #3: Hay dos vértices diagonalmente opuestos del rectángulo de área máxima que están 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 únicos dos vértices de límite fueran adyacentes, entonces el borde opuesto (cuyos vértices no están en el límite) podría ser extraído un poco, aumentando el área del rectángulo y contradiciendo su máximalidad.

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

Para probarlo, supongamos que ese no es el caso, es decir, que el rectángulo de á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, contradiciendo la máximalidad.

Llama a los vértices del rectángulo A, B, C y D. Sin pérdida de generalidad, supongamos que B y D son los dos que están en el límite del polígono. Dado que A y C están en el interior del polígono, hay algo de margen alrededor de ellos (representado con círculos alrededor de A y C en la imagen de abajo). Ahora dibuja un círculo alrededor del rectángulo, y desliza los puntos A y C un poco alrededor del círculo por la misma cantidad (para hacer A' y C', como se muestra abajo) para que el nuevo rectángulo A'BC'D sea más cuadrado que el rectángulo original. Este proceso crea un nuevo rectángulo que también está dentro del polígono original y tiene un área más grande. Esto es una contradicción, así que la demostración está hecha.

Para creer esa prueba, debes convencerte de que el área de un rectángulo inscrito en un círculo aumenta a medida que se vuelve "más cuadrado" (es decir, la diferencia entre las longitudes de los bordes disminuye). También necesitas que el polígono sea convexo para que las nuevas líneas estén todas dentro de él. Y probablemente hay otros pequeños detalles que se pasan por alto, pero estoy bastante seguro de que todos funcionan.

Answer 2

He hecho un boceto muy rápido y horroroso sobre tu nota verde en la pregunta. No pude enviarlo como comentario, así que tuve que escribir una respuesta, aunque no sea una.
Creo que en la imagen de abajo tenemos un rectángulo de área máxima (no es perfecto, es solo un boceto hecho en Paint para dar una idea), y no creo que puedas encontrar uno más grande que tenga un lado común con los bordes del polígono negro...
Sin embargo, puedo estar equivocado, en ese caso tienes todas mis disculpas.

Answer 3

La mayoría de otros algoritmos encuentran el rectángulo rectilíneo de área máxima inscrito en un polígono convexo, y tienen una complejidad de O(log n). No creo que tu suposición de que el polígono de área máxima esté alineado con uno de los lados sea correcta, porque todo lo que tendrías que hacer es rotar el polígono n veces, lo que resultaría en una complejidad de O(n log n), y en mi breve investigación no pude encontrar nada que indique que fuera tan fácil.

Sin embargo, el artículo Largest Inscribed Rectangles in Convex Polygons por Knauer, et. al., describe un algoritmo de aproximación que te acercará a la respuesta correcta.

Según mi mejor entendimiento del algoritmo, se basa en uno de los polígonos de área máxima alineados con un eje conocidos, y luego muestrea puntos aleatorios dentro del espacio poligonal, genera varios 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 de ese conjunto.

Answer 4

Tal vez eche un vistazo a esta implementación del rectángulo interior más grande. Utiliza el algoritmo descrito en este documento. Un ejemplo de imagen es