Tengo una matriz V[1,2,....,n], donde cada elemento de la matriz representa un vértice de un polígono convexo en forma de un par de coordenadas (x, y).

Se da que V[1] es el vértice con la coordenada x mínima y que los vértices V[1,2,....,n] están ordenados en sentido antihorario, como en la figura. También se da por hecho que las coordenadas x de los vértices son todas distintas, al igual que las coordenadas y de los vértices. ingrese la descripción de la imagen aquí

Ahora, quiero encontrar el vértice con el valor máximo de coordenadas y. Todos conocemos el método ingenuo de O (n), pero ¿es posible encontrarlo en O (log (n))?

Usé la información de que V[1] es el vértice con la coordenada x mínima para encontrar el vértice con la coordenada x máxima en el tiempo O (log (n)). Pero, ¿es posible hacerlo para la coordenada y máxima?

¡Gracias por la ayuda!

3
Ank 10 sep. 2018 a las 00:03

4 respuestas

La mejor respuesta

Versión larga

La búsqueda binaria se observa como la solución en algunos lugares aquí, pero solo funcionará en algunos casos.

La distribución de los vértices puede variar de varias maneras diferentes. Puede tener muchos agrupados cerca de un punto con uno aislado en otro lugar, podría tener vértices que formen una forma parabólica (tomando su diagrama, eliminar los vértices 7, 8 y 9 como ejemplo), podría tener una distribución de tipo logarítmico (p. Ej. solo vértices 1, 2, 3 y 4), o realmente cualquier otra cantidad de posibilidades. En todos estos casos diferentes, tendrá una cantidad y un desplazamiento diferentes de máximos y mínimos locales.

Lo más probable es que necesite una combinación de enfoques para estimar la distribución y luego la aplicación de una estrategia que se ajuste al tipo de distribución.

Tratemos de describir tal estrategia:

Primero, tenga en cuenta que tiene una serie de tales vértices, enumerados en un orden estricto en una rotación en sentido antihorario. Esto es importante y es la base de todos los supuestos y razonamientos posteriores.

Observe el comportamiento de V[n]. Si V[n] tiene una coordenada y V[n].y menor que la de V[1], o V[n].y < V[1].y, puede concluir que todos los demás vértices V[2, n-1] también deben tener y- coordenadas inferiores a V[1] (considere por qué este debe ser el caso). Por lo tanto, V[1] tiene la coordenada y más grande.

Ahora, el resto de este análisis requerirá que modifiquemos nuestro modelo conceptual del polígono para simplificar su representación y, por lo tanto, el problema que queremos resolver. En lugar de trazar los puntos (V[i].x, V[i].y) para obtener la forma del polígono, en lugar de trazar (i, V[i].y) para representar una función continua imaginada f(i) = V[i].y. La solución a nuestro problema ahora es la solución para encontrar el máximo global de la función f(i) = V[i].y.

Con eso en mente, para todos los demás casos donde V[n].y > V[1].y, debemos realizar una búsqueda binaria, pero tenemos dos escenarios posibles a considerar:

  1. V[2] tiene una coordenada y menor que V[1].
  2. V[2] tiene una coordenada y mayor que V[1].

Esto es importante porque el caso 1 nos dice que V[1] es no un mínimo local, y el caso 2 nos dice que V[1] es un mínimo local ( una vez más considere por qué este debe ser el caso).

El caso 2 es un caso agradable y fácil debido a que V[1] es un mínimo local. Esto significa que solo puede haber un mínimo local adicional en V[n], o no hay otro mínimo local en absoluto. Por lo tanto, podemos realizar una búsqueda binaria o binaria de tal manera que converjamos gradualmente en los únicos máximos locales en la curva.

Su diagrama es un ejemplo del caso 1, que es el caso más difícil. V[1] no es un mínimo local, por lo que es un máximo local. Más importante aún, tiene dos máximos locales posibles, que se encuentran en V[1] y V[n-k] donde n-k > 1. Para ayudar a visualizar, si traza los puntos para la función f(i) = V[i].y, verá una forma parabólica o una forma sinusoidal. El segundo máximo local en V[n-k] será, por lo tanto, el extremo más a la derecha de la parábola o el pico de la curva sinusoidal.

(Nota: este párrafo es un paso de optimización opcional). Consideremos cómo determinar qué tipo de máximos locales estamos tratando: si V[n] tiene una coordenada y mayor que {{ X1}}, entonces V[n] debe ser el segundo máximo local (nuevamente, considere por qué esto debe ser cierto) y, de hecho, podemos determinar instantáneamente que V[n] tiene la coordenada y más grande. De lo contrario, existen algunos k tales que V[n-k] es nuestro máximo local, lo que significa que debemos realizar una búsqueda.

Esto ahora solo nos deja con la consideración de cómo realizar la búsqueda, para evitar la convergencia inadvertida en V[1] (necesitamos encontrar un máximo local, y dado que V[1] es un máximo local en el que podríamos converger accidentalmente eso).

Realice una búsqueda binaria con las siguientes restricciones:

  • Para un V[i] dado, si V[i].y < V[1].y converge hacia V[n].
  • Si V[i].y > V[1].y converge en la dirección de aumentar y (solo compara V[i] con V[i-1] y V[i+1]).

Esto debería permitirle converger de manera segura hacia los máximos locales más a la derecha y aislar el valor dentro de log(n) tiempo.

Ahora que hemos cubierto los dos casos diferentes para V[1].y < V[n].y, tengamos en cuenta que esta búsqueda binaria restringida funcionará en el caso 2 con la misma precisión que en el caso 1. Por lo tanto, podemos generalizar la búsqueda para ambos casos 1 y el caso 2 siguiendo las reglas de la búsqueda binaria restringida para ambos casos. Esto reduce significativamente la complejidad algorítmica.

En total, debe poder alcanzar el tiempo O(log n) para cualquier caso general, con un par de O(1) casos extremos.

Resumen

El truco detrás de este problema es deconstruir la noción del polígono, trazando los puntos (i, V[i].y) en lugar de (V[i].x, V[i].y) e imaginando que esos puntos están en una función continua. La solución a este problema se convierte en la solución al problema "¿cuál es el máximo global de f(i) = V[i].y?". Debido a las propiedades de un polígono convexo y la forma en que se ordenan sus vértices, podemos determinar que V[1] es definitivamente un máximo local. Con eso en mente, V[1] es el máximo global o no lo es, algo que podemos determinar en tiempo constante desde el principio. Si no es el máximo global, entonces podemos realizar una búsqueda binaria restringida que nos impide converger en V[1], lo que nos permite determinar el máximo global en tiempo logarítmico. Si queremos ser más sofisticados, también podemos determinar si V[n] es el máximo global en tiempo constante como un paso de optimización adicional.


Versión corta

Cuando V[1].y > V[n].y, el máximo es V[1].y. Su solución debe usar una búsqueda binaria en casos donde V[1].y < V[n].y solamente. Esta búsqueda binaria debe cumplir con las siguientes restricciones, dado un V[i] arbitrario:

  • Caso base: si V[1].y > V[i].y, converge en la dirección de V[n].
  • Caso estándar: si V[i].y < V[i+1].y, converge en la dirección de V[n]; de lo contrario, si V[i].y < v[i-1].y, converge en la dirección de V[1]; sino V[i].y es el máximo.

También hay una optimización opcional que se puede realizar para el caso límite donde V[1].y < V[n].y y V[n].y > V[n-1].y. Esta optimización se puede omitir de forma segura y puede simplificar la conceptualización y la implementación de la solución.

El pseudocódigo para el algoritmo correspondiente es el siguiente:

Solución con optimización

Si V[1].y > V[n].y, entonces V[1].y es el máximo.

Si V[1].y < V[n].y y V[n].y > V[n-1].y, entonces V[n].y es el máximo.

Si V[1].y < V[n].y y V[n].y < V[n-1].y, realice la búsqueda binaria restringida.

Esta estrategia tiene dos O(1) casos extremos y un caso estándar O(log n).

Solución sin optimización

Si V[1].y > V[n].y, entonces V[1].y es el máximo.

Si V[1].y < V[n].y, realice la búsqueda binaria restringida.

Esta estrategia tiene un caso de borde O(1) y un caso estándar O(log n).

2
B. Fleming 10 sep. 2018 a las 08:01

Sea V [m] el vértice con la coordenada y máxima.

El caso más simple a considerar es m=1, cuando V[2].y < V[1].y > v[n].y. Dado que la exclusión de este caso simplifica el razonamiento posterior, asumiremos que se realiza una verificación inicial para este caso.

Considere un borde E [i] con origen V [i], donde 1<i<=n. Dada la restricción de que todas las coordenadas xey son distintas, E [i] tiene que estar en uno de los 4 cuadrantes planos:

enter image description here

Dado que hemos excluido el caso donde m=i=1, para E [i] que se encuentra en los Cuadrantes I, II o IV, debe ser el caso de que m>i. Si E [i] se encuentra en el Cuadrante III, entonces m=i, lo cual es cierto si V[i].y > V[i-1].y o m<i.

Podemos usar este razonamiento como base para una búsqueda binaria, donde en cada iteración realizamos:

if E[i] lies in Quadrant III
   if V[i].y > V[i-1].y then m=i
   else consider left half
else
   consider right half

Aquí hay un código Java para ilustrar:

static Point maxY(Point[] v)
{       
    // check for max at origin
    if(v[1].y < v[0].y && v[v.length-1].y < v[0].y)
    {
        return v[0];
    }

    int left = 0; 
    int right = v.length-1;     
    Point maxY = null;
    while(left <= right)
    {
        int mid = left + (right-left)/2;
        if(v[(mid+1)%v.length].y < v[mid].y && v[(mid+1)%v.length].x < v[mid].x)
        {
            // Quadrant III
            if(v[mid].y > v[mid-1].y) 
            {
                maxY = v[mid];
                break;
            }
            right = mid - 1;
        }
        else 
        {
            left = mid + 1;
        }
    }
    return maxY;
}

Y algunos casos de prueba simples:

public static void main(String[] args)
{
    Point[][] tests = {
            {new Point(0, 10), new Point(10, 0), new Point(9, 5)},
            {new Point(0, 0), new Point(9, 5), new Point(10, 10)},
            {new Point(0, 0), new Point(10, 10), new Point(5, 8)},
            {new Point(0, 5), new Point(9, 0), new Point(10, 10)},
            {new Point(0, 5), new Point(6,0), new Point(10, 6), new Point(5,10)}};

    for(Point[] coords : tests) 
        System.out.println(maxY(coords) + " : " + Arrays.toString(coords));
}

Salida:

(0, 10) : [(0, 10), (10, 0), (9, 5)]
(10, 10) : [(0, 0), (9, 5), (10, 10)]
(10, 10) : [(0, 0), (10, 10), (5, 8)]
(10, 10) : [(0, 5), (9, 0), (10, 10)]
(5, 10) : [(0, 5), (6, 0), (10, 6), (5, 10)]
0
SirRaffleBuffle 10 sep. 2018 a las 07:04

Debido a que el polígono es convexo, el ángulo del vector entre puntos sucesivos aumenta monotónicamente de 270 grados (hacia abajo, llame a eso -90 grados) hasta 0 (derecha), 90 (arriba), 180 (izquierda), etc., a medida que se mueve de un punto al siguiente alrededor del polígono.

Por lo tanto, puede realizar una búsqueda binaria para encontrar el ángulo más pequeño mayor de 180 grados. El punto donde el vector hasta el siguiente punto se convierte en> 180 grados (V [8] en su ejemplo) es donde el polígono gira de arriba hacia abajo o de izquierda a abajo, y ese punto debe tener la coordenada Y más grande.

Creo que el artículo al que se vinculó Peter dice lo mismo, pero son muchas palabras para leer para una idea tan simple.

1
Matt Timmermans 9 sep. 2018 a las 23:32

Puede encontrar el punto extremo en cualquier dirección utilizando una búsqueda binaria como se describe aquí.

La idea esencial es examinar el vector en los puntos finales y el punto medio y usar esto para determinar qué parte expandir.

1
Peter de Rivaz 9 sep. 2018 a las 21:18