¿Algoritmo de casco convexo dinámico sublineal pero simple?

Question

Necesito resolver el problema del algoritmo de casco convexo dinámico, es decir, mantener el casco convexo de los puntos 2D, donde puedo agregar y eliminar puntos.

El enfoque ingenuo es claramente O(N); cada vez que se agrega/elimina uno de los puntos N, recalculamos el casco convexo desde cero. Sin embargo, no puedo permitirme el tiempo lineal, entonces estoy buscando un algoritmo sublineal. Hasta ahora, he encontrado un montón de papel que describen un algoritmo sofisticado con límites de tiempo locos que tardarían siglos en implementarse. Incluso el algoritmo eficiente más antiguo, debido a Overmars y Leeuween, que es O(log^2 N) parece demasiado complicado. (Como es habitual, la mayor parte de los algoritmos descritos en esos documentos tienen toneladas de dependencias en términos de estructuras/algoritmos de otros documentos, referenciados)

Estoy buscando algo más simple, no necesariamente novela, que lleva a cabo mejor que lineal en el el peor caso (por ejemplo, O(sqrt N)). Finalmente, no me importa si el tiempo se amortiza. ¿Algunas ideas?

(Por simple, me refiero sobre todo algo que no requiere más que unos pocos cientos de líneas de código.)

Answer 1

Creo que lo que busca no existe. El algoritmo Overmars y vanLeeuwen no es tan complicado, y parece necesario en cierto sentido. Primero, cambie el problema para mantener el casco superior y el casco inferior por separado. En segundo lugar, construya cada uno dividiendo y conquistando, pero conserve las estructuras de árbol intermedias, de modo que conozca los cascos de los conjuntos de 1/2, los conjuntos de 1/4, etc. Ahora, cuando elimina un punto, vuelva a calcular solo sus antepasados ​​en el árbol. Cuando agrega un punto, descubre a qué hoja se une, y vuelve a calcularlo nuevamente hacia la raíz.

Creo que si ignora los detalles en su documento, sigue este boceto de alto nivel e implementa todos los pasos de la manera más descerebrada, no será complicado y será sublineal.

---

M. H. Overmars y J. van Leeuwen. Mantenimiento de configuraciones en el avión. J. Comput. Syst. Sci., 23: 166-204, 1981.

Answer 2

Supongo que hay N puntos de datos en total y que el complejo casco está definido por M puntos.

Debería ser mucho más fácil (y menos costoso) mantener un casco convexo que construirlo en primer lugar.

Extracción de un punto de datos existente

1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it. 

2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4 

Adición de un nuevo punto de datos.

3/ If a data point is inside the complex hull then it will not affect the hull. 

Aquí está una manera simple de probar esto de la parte superior de mi cabeza. Crea una triangulación del interior del casco. Un casco complejo definido usando M puntos se puede triangular en triángulos M-2. Luego prueba si el punto se encuentra en uno de los triángulos.

4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it. 

no veo cómo cualquiera de este mantenimiento puede ser O (N)

Answer 3

Con respecto al Prof.O'Rourke, que sabe mucho más que yo sobre geometría computacional, no veo cómo una implementación "sin sentido" de OvL (es decir, una falta de reequilibrio) podría ser sublineal en el peor de los casos.

Afortunadamente, hemos realizado algunos avances en las estructuras de datos desde 1981. En particular, dado que una garantía amortizada es suficiente, los árboles splay (1985) son apropiados para almacenar tanto cascos convexos como el árbol de fusión. Austern et al. (2003) propuso una buena manera de separar el mantenimiento de los campos adicionales que se requerirán de las complejas operaciones de balanceo, para que pueda escribir las partes complicadas una vez.

La principal dificultad en la implementación de árboles de separación es la operación de separación, e incluso eso es mucho más simple que, por ejemplo, insertar en un árbol rojo-negro. Una vez que splay funciona, los árboles de configuración son fácil para dividir y unir. Para dividir, amplíe el nodo que desea dividir después y corte a su hijo derecho. Para unirse, despliega el nodo derecho del primer árbol y convierte el segundo árbol en el hijo derecho de ese nodo.