Recinto de área máxima dada la longitud de los lados

Question

Un compañero me planteó el siguiente problema :

Dada una secuencia de $n$ longitudes (es decir, $L_1, L_2, .., L_n$ ) donde cada una es la longitud del lado, encontrar una secuencia de $n$ puntos (donde $p_k = (x_k, y_k)$ ) tal que $dist(p_k, p_{k+1}) = L_k$ y $dist(p_1, p_n) = L_n$ donde $dist(a, b)$ es la distancia euclidiana entre los puntos $a$ y $b$ .

Tenga en cuenta que el primer punto , $p1$ , debe ser $(0, 0)$ y el segundo punto , $p_2$ , debe ser $(0, L_1)$ .

Estos puntos deben corresponder a los vértices ordenados en el sentido de las agujas del reloj del polígono simple que tenga la máxima área posible para las longitudes de los lados dadas.

Determina las coordenadas de los puntos que corresponden a un polígono de área máxima.

Ahora bien, he visto algunos problemas similares, pero con este no sé ni cómo empezar. Determinar el área máxima es bastante fácil por la fórmula de Brahmagupta, pero el hallazgo real de los puntos parece realmente difícil.

Lo único que se me ocurre es encontrar algún tipo de círculo envolvente y luego tratar de determinar los puntos, pero eso no es ni siquiera un punto de partida.

¿Alguna idea sobre cómo solucionar esto?

Answer 1

(Por lo que veo, el concurso en línea ya ha terminado, así que volveré a publicar mi respuesta como había prometido).

---

Según lo comentado por hardmath, y acordado por el OP, la solución es un polígono cíclico cuyos vértices se encuentran en un círculo común.

Obsérvese que si uno de los segmentos de la línea fuera más largo que la suma de la longitud del resto de los segmentos de la línea, no pueden formar un polígono. Por ello, sabemos que $$L_i \le \sum_{k \ne i}^{n} L_k$$ para todos $i = 1 \ldots n$ . (Esto también significa que $0 \le \theta_i \lt \pi$ .)

Cada uno de los $n$ segmentos de línea forma esencialmente un triángulo isósceles con el centro del círculo común. Dos de los lados son de longitud $r$ el radio del círculo común, y el tercero es el propio segmento de línea, de longitud $L_i$ . (Esencialmente, podemos descomponer el polígono en cuñas triangulares, siendo cada una de ellas un triángulo isósceles. Esto también significa que el orden de los segmentos de línea no afecta al área, ya que reordenar las partes triangulares no cambia sus áreas).

La longitud de un cuerda circular cumple con $$L_i = 2 r \sin\left(\frac{\theta_i}{2}\right)$$ Aquí, $\theta_i$ es el ángulo entre el $r$ -cantos de longitud en los triángulos isósceles. Resolviendo para $\theta_i$ vemos que $$\theta_i = 2 \arcsin \left( \frac{L_i}{2 r} \right) = \arccos \left( 1 - \frac{ L_i^2 }{2 r^2} \right)$$ porque $2 \arcsin(x) = \arccos(1 - 2 x^2)$ cuando $0 \le x \le 1$ .

Tenga en cuenta que esto también significa que $$\frac{d \, \theta_i}{d \, r} = - \frac{2 L}{\sqrt{4 r^4 - L^2 r^2}}$$

Para que la figura sea un polígono, la suma de los ángulos $\theta_i$ debe ser igual a $180°$ : $$\sum_{i=1}^{n} \theta_i = 2 \pi$$

Combinando las dos anteriores, y dividiendo por dos, obtenemos $$\sum_{i=1}^{n} \arcsin \left( \frac{L_i}{2 r} \right) = \pi$$ que podemos utilizar para numéricamente resolver para $r$ .

Para que cada $\theta_i$ de existir, $\max(L)/(2r) \le 1$ . Esto significa que $r \ge \max(L)/2$ y que $r_{min} = \max(L)/2$ es el radio mínimo permitido en los métodos numéricos.

También sabemos que el radio debe ser menor que la mitad del perímetro, por lo que $r_{max} = (\sum_i L_i) / 2$ .

Cuando hayamos encontrado el $r$ para lo cual $\sum_i \theta_i = 2 \pi$ podemos calcular las coordenadas de los vértices. Como los puntos deben estar en el orden de las agujas del reloj, podemos utilizar $$\begin{cases} x_i' = x_0 - r \cos \varphi_i \\ y_i' = y_0 + r \sin \varphi_i \\ \end{cases}$$ donde $$\begin{cases} x_0 = r \cos \varphi_1 \\ y_0 = -r \sin \varphi_1 \end{cases}$$ y $$\varphi_i = \begin{cases} -\frac{\theta_i}{2}, & i = 1 \\ -\frac{\theta_i}{2} + \sum_{k=1}^{i-1} \theta_i, & 2 \le i \le n \end{cases}$$ Lo anterior nos da $\varphi_1 = -\theta_1/2$ y $\varphi_2 = -\varphi_1 = \theta_1/2$ , por lo que el primer segmento de línea será vertical; $x_1 = x_2 = y_1 = 0$ , $y_2 \gt 0$ (de hecho $y_2 = L_1$ ).

Por lo tanto, lo anterior da como resultado $x_1 = 0$ , $y_1 = 0$ , $x_2 = 0$ , $y_2 = L_1$ con el resto de los vértices $(x_i, y_i)$ en el sentido de las agujas del reloj alrededor del centro en $(x_0, y_0)$ .

---

Este es un programa de ejemplo que lee las longitudes de las líneas desde la entrada estándar, y utiliza una búsqueda binaria para encontrar el radio con al menos seis dígitos de precisión, dando salida a las coordenadas de los vértices en la salida estándar. ejemplo.c :

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define  PI     3.141592653589793238462643383279502884197
#define  TWO_PI 6.283185307179586476925286766559005768394

double theta(const double L, const double r)
{
    return 2.0 * asin(0.5 * L / r);
}

double d_theta(const double L, const double r)
{
    const double r2 = r * r;
    return -2.0 * L / (r2 * sqrt(4.0 - L * L / r2));
}

double find_radius(const double length[], const size_t count, const double epsilon, size_t *iteration_count)
{
    const double min_theta = 1.0 - epsilon;
    const double max_theta = 1.0 + epsilon;

    double sum_length = length[0];
    double max_length = length[0];
    double min_radius, radius, max_radius;
    size_t iterations = 0;
    size_t i;

    for (i = 1; i < count; i++) {
        sum_length += length[i];
        if (max_length < length[i])
            max_length = length[i];
    }

    min_radius = 0.5 * max_length;
    max_radius = 0.5 * sum_length;

    while (1) {
        double sum_theta = 0.0;

        iterations++;

        radius = (0.5 * min_radius) + (0.5 * max_radius);

        for (i = 0; i < count; i++)
            sum_theta += theta(length[i], radius);

        sum_theta /= TWO_PI;

        if (sum_theta >= min_theta && sum_theta <= max_theta)
            break;
        else
        if (sum_theta < 1.0)
            max_radius = radius;
        else
            min_radius = radius;
    }

    if (iteration_count)
        *iteration_count = iterations;

    return radius;
}

int main(void)
{
    double  *line_length   = NULL;
    size_t   line_count    = 0;
    size_t   line_maxcount = 0;
    double   radius, phi, x, y, x0, y0;
    size_t   i;

    /* Read line lengths from standard input. */
    while (1) {
        char   buffer[1024], *line;
        double length;

        line = fgets(buffer, sizeof buffer, stdin);
        if (!line)
            break;

        if (sscanf(line, " %lf", &length) < 1)
            break;

        if (length <= 0.0)
            break;

        if (line_count >= line_maxcount) {
            const size_t maxcount = (line_count | 255) + 257;
            double      *temp;

            temp = realloc(line_length, maxcount * sizeof line_length[0]);
            if (!temp) {
                fprintf(stderr, "Out of memory.\n");
                return EXIT_FAILURE;
            }

            line_length = temp;
            line_maxcount = maxcount;
        }

        line_length[line_count++] = length;
    }

    /* Verify sanity. */
    if (line_count >= 3) {
        double max_length = line_length[0];
        double sum_length = line_length[0];

        for (i = 1; i < line_count; i++) {
            sum_length += line_length[i];
            if (max_length < line_length[i])
                max_length = line_length[i];
        }

        if (max_length > sum_length - max_length) {
            fprintf(stderr, "Not a valid polygon; one of the line segments is too long.\n");
            return EXIT_FAILURE;
        }
    } else {
        fprintf(stderr, "Need at least three line lengths.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Read %zu line lengths:\n", line_count);
    for (i = 0; i < line_count; i++)
        fprintf(stderr, "\t%.6f\n", line_length[i]);

    radius = find_radius(line_length, line_count, 0.0000002, &i);

    fprintf(stderr, "radius = %.6f using %zu iterations.\n", radius, i);

    phi = -0.5 * theta(line_length[0], radius);

    x0 = radius * cos(phi);
    y0 = -radius * sin(phi);

    for (i = 0; i < line_count; i++) {
        x = x0 - radius * cos(phi);
        y = y0 + radius * sin(phi);
        phi += theta(line_length[i], radius);
        printf("%.6f %.6f\n", x, y);
    }

    return EXIT_SUCCESS;
}

Compilarlo utilizando, por ejemplo, en Linux

gcc -Wall -O2 example.c -lm -o example

y ejecutarlo, generando digamos 10 longitudes de línea aleatorias como entrada, utilizando

awk 'BEGIN { srand(); for (i=0; i<10; i++) printf "%.6f\n", 10.0*rand() }' | ./example

Aquí hay un ejemplo de la salida, las primeras 12 líneas al error estándar, seguidas por 10 líneas a la salida estándar:

Read 10 line lengths:
    1.487793
    5.241667
    2.002344
    4.271945
    7.815320
    5.452837
    6.012328
    7.506031
    3.599992
    1.636063
radius = 7.377844 using 19 iterations.
0.000000 0.000000
0.000000 1.487793
2.346549 6.174880
3.990793 7.317614
8.195604 8.071990
14.300092 3.191984
14.080471 -2.256429
9.609570 -6.276271
2.286102 -4.630880
0.344424 -1.599406

Answer 2

Voy a añadir algunas observaciones sobre la configuración y la solución para circunscribiendo diámetro $d$ de la que se puede obtener el área máxima (del polígono cíclico).

(0) El caso $n=3$ es resuelto directamente utilizando la fórmula de Heron para el área del triángulo. El caso $n=4$ también tiene una solución directa, pero es menos conocido . Para $n \gt 4$ presentamos un enfoque iterativo (solución de una ecuación no lineal).

(1) El orden de las longitudes de las cuerdas (lados del polígono) no afecta al área máxima que puede alcanzar el polígono. Hay una buena prueba de esto mediante la transposición de las cuerdas adyacentes, mostrando que cualquier permutación de lados en un polígono cíclico preserva el área.

(2) Incluso si se especifica un orden de las longitudes de los lados $L_1,L_2,\ldots,L_n$ podemos sin pérdida de generalidad disponer (por rotación) que $L_1$ es el máximo de estos. Entonces la comprobación $L_1 \lt \sum_{i=2}^n L_i$ garantiza la existencia de un polígono con área positiva.

(3) El diámetro $d$ del círculo debe ser al menos la longitud máxima de la cuerda $L_1$ . Hay dos casos distinguibles en los que el diámetro supera estrictamente $L_1$ . O bien todos los vértices se encuentran en un semicírculo (y el centro del círculo está fuera del polígono), o bien el centro del círculo estará en el interior del polígono.

(4) Un buen primer paso para resolver el radio (equiv. el diámetro) del círculo distingue cuál de esas disposiciones es factible. Para los lados $L_i$ con $i\gt 1$ , definir la suma de medio los ángulos que subtendrán en un círculo de diámetro (aún indeterminado) $d$ :

$$ \Theta(d) := \sum_{i=2}^n \sin^{-1} (L_i/d) $$

(5) Si $\Theta(L_1) = \pi/2$ entonces $d=L_1$ es la solución, y además la cuerda del diámetro $L_1$ , las otras cuerdas se inscriben en su semicírculo.

(6) Si $\Theta(L_1) \lt \pi/2$ , entonces la factible $d$ superará $L_1$ pero todos los vértices estarán en un semicírculo, con la cuerda más larga $L_1$ puente a través de los acordes más pequeños. La ecuación no lineal a satisfacer es entonces:

$$ \Theta(d) = \sin^{-1} (L_1/d) $$

(7) Si $\Theta(L_1) \gt \pi/2$ , entonces la factible $d$ superará $L_1$ pero no todos los vértices estarán en un semicírculo, y por tanto el centro del círculo estará en el interior del polígono cíclico. Así, los ángulos centrales subtendidos por las cuerdas sumarán $2\pi$ y en términos de nuestra $\Theta(d)$ notación, la ecuación no lineal a resolver es:

$$ \Theta(d) = \pi - \sin^{-1} (L_1/d) $$

Ejemplo

Considera las longitudes, ordenadas como en el caso anterior, de modo que la longitud más larga vaya en primer lugar:

$$ 10, 8, 2, 5, 6, 4, 8, 5, 4, 2 $$

El cheque $\Theta(10) \approx 4.771 \gt \pi/2$ nos dice que los vértices girarán alrededor del centro del círculo, por lo que según (7) la ecuación no lineal a satisfacer es:

$$ \sin^{-1}(L_1/d) + \Theta(d) = \pi $$

Simplifica las derivadas (necesarias para el método de Newton) si hacemos el cambio de variable $z = L_1/d$ por lo que la ecuación se convierte en..:

$$ F(z) := \sin^{-1}(z) + \sum_{i=2}^n \sin^{-1}(\alpha_i z) = \pi $$

donde $\alpha_i = L_i/L_1$ . Para $z\in (0,1)$ obtenemos su derivada:

$$ F'(z) = (1-z^2)^{-1/2} + \sum_{i=2}^n \alpha_i(1 - \alpha_i^2 z^2)^{-1/2} $$

Tenga en cuenta que $F(z)$ es continua, monótona y creciente en $[0,1]$ . Ahora $F(0) = 0$ y también sabemos como resultado de la comprobación $\Theta(10) \gt \pi/2$ que $F(1) \gt \pi$ . Por lo tanto, una raíz de $F(z) = \pi$ existirá "en el medio" por IVT .

A menudo se utilizan uno o dos pasos de un método convergente de bajo orden, como la bisección o el método secante, para "acercarse" a la raíz antes de aplicar un método de Newton. Un paso de bisección equivale a comprobar $F(1/2) \approx 2.760 \lt \pi$ por lo que nuestra búsqueda de la raíz debe limitarse a $z\in [1/2,1]$ .

Desde $F(1/2) \approx 2.760$ y $F(1) \approx 6.342$ , un paso de el método secante (interpolación lineal) da una aproximación de la raíz cerca:

$$ z_0 = \frac{(1/2)(F(1)-\pi) - (1)(F(1/2)-\pi)}{F(1)-F(1/2)} \approx 0.5533 $$

que adoptamos como conjetura inicial para el método de Newton:

$$ z_{k+1} = z_k - \frac{F(z_k) - \pi}{F'(z_k)} $$

Una tabla de algunos iterados posteriores, calculada con Google Sheets, muestra una rápida convergencia:

$$ \begin{array}{c|c|c|c} k & z_k & F(z_k) & F'(z_k) \\ \hline 1 & 0.5533006452 & 3.070530159 & 5.884332671 \\ 2 & 0.5653772049 & 3.141749930 & 5.910562711 \\ 3 & 0.5653505955 & 3.141592654 & 5.910503695 \\ 4 & 0.5653505954 & 3.141592654 & 5.910503695 \end{array} $$

Para el método de Newton es típico que los iterados se asienten rápidamente al acercarse al límite por un lado (como hicieron en este caso).

Recordemos que $z = L_1/d$ y por lo tanto $d = L_1/z \approx 17.68813915$ . La conversión de diámetro a radio da como resultado $r \approx 8.844069575$ .