Maksima zbioru punktów
W geometrii obliczeniowej o punkcie p w skończonym zbiorze punktów S mówi się, że jest maksymalny lub niedominowany , jeśli nie ma innego punktu q w S , którego wszystkie współrzędne są większe lub równe odpowiednim współrzędnym p . Maksima zbioru punktów S to wszystkie punkty maksymalne zbioru S . Problem znalezienia wszystkich punktów maksymalnych, nazywany czasem problemem maksimów lub problem zbioru maksimów , był badany jako wariant problemów z kadłubem wypukłym i ortogonalnym z kadłubem wypukłym . Jest to równoznaczne ze znalezieniem granicy Pareto zbioru punktów i zostało nazwane problemem płynnej waluty przez Herberta Freemana w oparciu o aplikację polegającą na porównaniu względnego bogactwa osób z różnymi zasobami wielu walut.
Dwa wymiary
W przypadku punktów w dwóch wymiarach problem ten można rozwiązać w czasie O ( n log n ) za pomocą algorytmu wykonującego następujące kroki:
- Posortuj punkty w jednym z wymiarów współrzędnych ( powiedzmy współrzędna x )
- Dla każdego punktu, w porządku malejącym o współrzędną x , sprawdź, czy jego współrzędna y jest większa niż maksymalna współrzędna y dowolnego wcześniej przetworzonego punktu. (Jeśli chodzi o pierwszy punkt, jest to bezsensowna prawda ). Jeśli tak, wypisz punkt jako jeden z punktów maksymalnych i zapamiętaj jego y jako największą, jaką do tej pory zaobserwowano.
Jeśli przyjmuje się, że współrzędne punktów są liczbami całkowitymi , można to przyspieszyć za pomocą algorytmów sortowania liczb całkowitych , aby mieć taki sam asymptotyczny czas działania jak algorytmy sortowania.
Trzy wymiary
W przypadku punktów w trzech wymiarach ponownie możliwe jest znalezienie maksymalnych punktów w czasie O ( n log n ) za pomocą algorytmu podobnego do algorytmu dwuwymiarowego, który wykonuje następujące kroki:
- Posortuj punkty w jednym z wymiarów współrzędnych ( powiedzmy współrzędna x )
- Dla każdego punktu, w porządku malejącym o współrzędną x , sprawdź, czy jego rzut na płaszczyznę yz jest maksymalny spośród zbioru rzutów zbioru punktów przetworzonych do tej pory. Jeśli tak, wypisz punkt jako jeden z punktów maksymalnych i zapamiętaj jego y jako największą, jaką zaobserwowano do tej pory.
Ta metoda redukuje problem obliczania maksymalnych punktów statycznego trójwymiarowego zbioru punktów do problemu utrzymywania maksymalnych punktów dynamicznego dwuwymiarowego zbioru punktów. Dwuwymiarowy podproblem można skutecznie rozwiązać, stosując zrównoważone drzewo wyszukiwania binarnego w celu utrzymania zbioru maksimów dynamicznego zbioru punktów. Korzystając z tej struktury danych, można sprawdzić, czy nowy punkt jest zdominowany przez istniejące punkty, znaleźć i usunąć wcześniej niezdominowane punkty, które są zdominowane przez nowy punkt oraz dodać nowy punkt do zbioru punktów maksymalnych , w czasie logarytmicznym na punkt. Liczba operacji drzewa wyszukiwania jest liniowa w ciągu algorytmu, więc całkowity czas jest liniowy O ( n log n ) .
W przypadku punktów o współrzędnych całkowitych pierwsza część algorytmu, sortowanie punktów, może zostać ponownie przyspieszona przez sortowanie liczb całkowitych. Jeśli punkty są sortowane oddzielnie według wszystkich trzech wymiarów, zakres wartości ich współrzędnych można zredukować do zakresu od 1 do n bez zmiany względnej kolejności dowolnych dwóch współrzędnych i bez zmiany tożsamości punktów maksymalnych. Po tej redukcji w przestrzeni współrzędnych problem utrzymania dynamicznego dwuwymiarowego zbioru punktów maksymalnych można rozwiązać za pomocą drzewa van Emde Boasa zamiast zrównoważonego drzewa wyszukiwania binarnego. Te zmiany w algorytmie przyspieszają jego czas działania do O ( n log log n ) .
Wyższe wymiary
W dowolnym wymiarze d problem można rozwiązać w czasie O ( dn 2 ) , testując wszystkie pary punktów pod kątem tego, czy jedna z nich dominuje nad drugą, i zgłaszając jako wynik punkty, które nie są zdominowane. Jednakże, gdy d jest stałą większą niż trzy, można to poprawić do O ( n (log n ) d - 3 log log n ) . Dla zbiorów punktów, które są generowane losowo, możliwe jest rozwiązanie problemu w czasie liniowym .