Algoritmo. Área mínima de una plaza que encierra dado el conjunto de puntos.

Question

Estoy aprendiendo acerca de la ciencia de algoritmos y estoy estudiando algunos problemas con sus óptima del algoritmo. El problema que se describe a continuación es uno de ellos.

Necesito un inferior y un límite superior de su tiempo de ejecución de la complejidad. ¿Cuál es su óptimo algoritmo? No se necesita ninguna aplicación.

Problema:

Dado un conjunto de coordenadas en un plano bidimensional, ¿Cómo se encuentra el área de un mínimo de cuadrados que incluye todos los puntos. Los puntos pueden existir en la frontera también. Y la plaza de la orientación doen no tienen que ser paralelos a los ejes cartesianos.

Por ejemplo,

Considerar los puntos $(-1,1)$, $(1,3)$, $(0,2)$, $(-2,2)$. El mínimo cuadrado de la altura para cubrir estos puntos es $2\sqrt{2}$. Por lo tanto el área es $8$.

Espero que la explicación es clara. Gracias de antemano!

Answer 1

Editar:

El lema de abajo es falso, como por @BrianTung 's comentario.

La pregunta es muy interesante, incluso para un triángulo. Allí se puede demostrar que al menos un vértice debe ser un vértice de la mínima que contiene la plaza, y que para un triángulo obtusángulo el cuadrado cuya diagonal es el lado más largo que hace el trabajo. Para más información sobre el triángulo problema, ver

Cuadrado más pequeño que contiene un triángulo dado.

---

Todo lo que de aquí en está en desuso.

Pensamientos hacia una respuesta, modulo un lexema.

An edge of the minimal area square will contain an edge of the convex hull.

(Que es conocido por el mínimo rectángulo delimitador.)

Para encontrar el convex hull, en el tiempo $O(n \log n)$. (https://en.wikipedia.org/wiki/Convex_hull_algorithms), Entonces el bucle en cada uno de los en la mayoría de las $n$ bordes de la convex hull, encontrar el mínimo de delimitación de la plaza que contiene ese borde, en el tiempo en la mayoría de los $n$.

Que sería una $O(n^2 + n \log n) = O(n^2)$ algoritmo, posiblemente, incluso más rápido.

Ver http://www.uni-kiel.de/psychologie/rexrepos/posts/diagBounding.html para R código.