En geometría computacional , se dice que un punto p en un conjunto finito de puntos S es máximo o no dominado si no hay otro punto q en S cuyas coordenadas sean todas mayores o iguales que las coordenadas correspondientes de p . Los máximos de un conjunto de puntos S son todos los puntos máximos de S. El problema de encontrar todos los puntos máximos, a veces llamado problema de los máximos o problema del conjunto de máximos , se ha estudiado como una variante de los problemas de la envoltura convexa y de la envoltura convexa ortogonal . Es equivalente a encontrar la frontera de Pareto de una colección de puntos, y Herbert Freeman lo llamó el problema de la moneda flotante basándose en una aplicación que implica comparar la riqueza relativa de individuos con diferentes tenencias de múltiples monedas. [1]
Para puntos en dos dimensiones, este problema se puede resolver en tiempo O ( n log n ) mediante un algoritmo que realiza los siguientes pasos: [1] [2]
Si se supone que las coordenadas de los puntos son números enteros , esto se puede acelerar utilizando algoritmos de ordenamiento de números enteros , para tener el mismo tiempo de ejecución asintótico que los algoritmos de ordenamiento. [3]
Para puntos en tres dimensiones, nuevamente es posible encontrar los puntos máximos en el tiempo O ( n log n ) utilizando un algoritmo similar al bidimensional que realiza los siguientes pasos:
Este método reduce el problema de calcular los puntos máximos de un conjunto de puntos tridimensional estático a uno de mantenimiento de los puntos máximos de un conjunto de puntos bidimensional dinámico. El subproblema bidimensional se puede resolver de manera eficiente utilizando un árbol de búsqueda binario balanceado para mantener el conjunto de máximos de un conjunto de puntos dinámico. Utilizando esta estructura de datos, es posible probar si un nuevo punto está dominado por los puntos existentes, encontrar y eliminar los puntos previamente no dominados que están dominados por un nuevo punto, y agregar un nuevo punto al conjunto de puntos máximos, en tiempo logarítmico por punto. El número de operaciones del árbol de búsqueda es lineal a lo largo del algoritmo, por lo que el tiempo total es O ( n log n ) . [1] [2]
Para los puntos con coordenadas enteras, la primera parte del algoritmo, la ordenación de los puntos, se puede acelerar nuevamente mediante la ordenación de enteros. Si los puntos se ordenan por separado según sus tres dimensiones, el rango de valores de sus coordenadas se puede reducir al rango de 1 a n sin cambiar el orden relativo de dos coordenadas y sin cambiar las identidades de los puntos máximos. Después de esta reducción en el espacio de coordenadas, el problema de mantener un conjunto dinámico bidimensional de puntos máximos se puede resolver utilizando un árbol de van Emde Boas en lugar del árbol de búsqueda binaria balanceado. Estos cambios en el algoritmo aceleran su tiempo de ejecución a O ( n log log n ) . [3]
En cualquier dimensión d, el problema se puede resolver en tiempo O ( dn 2 ) probando todos los pares de puntos para ver si uno domina a otro y reportando como salida los puntos que no están dominados. Sin embargo, cuando d es una constante mayor que tres, esto se puede mejorar a O ( n (log n ) d − 3 log log n ) . [4] Para conjuntos de puntos que se generan aleatoriamente, es posible resolver el problema en tiempo lineal . [5] [6]