Algorytm dla maksymalnego zestawu zdominowanego

Question

FInd algorytm dla następnego problemu: Biorąc pod uwagę zestaw S n punktów w płaszczyźnie 2D, punkt (x1, y1) dominuje inny punkt (x2, y2), jeśli x1> x2 i y1> y2. Znajdź największy zestaw punktów M taki, że M jest podzbiorem S i żaden punkt M nie jest zdominowany przez inny punkt S.

Answer 1

Sortuj wszystkie punkty, zwiększając współrzędne x. Jeśli dwa punkty mają tę samą współrzędną x, posortuj je, zmniejszając współrzędne y. Teraz można pokazać, że podzbiór punktów jest zdominowany wtedy i tylko wtedy, gdy ich współrzędne y są nie rosnące w naszej posortowanej sekwencji, co oznacza, że ​​każda współrzędna y jest mniejsza lub równa poprzedniej w podciągnięciu.

Więc algorytm będzie:

1. Uporządkuj punkty jak opisano powyżej. Czas: O (n * logn).
2. Znajdź najdłuższy nie zwiększający się podciąg współrzędnych y. Czas: O (n * logn). Można to zrobić, dostosowując algorytm do znajdowania longest increasing subsequence.

Daje to największy możliwy zestaw w O (n * logn).

Answer 2

Istnieje algorytm dziel i podbijaj, który wykonuje to w czasie O (n * logn).

Podzielmy punkty na dwie połówki, o wielkości n/2 każda, na podstawie ich współrzędnych x. W obu połowach znajdujemy niedominowany punkt. Musisz zauważyć, że wszystkie niedominowane punkty znalezione w prawej połowie pojawią się na naszej ostatecznej liście.

Dzięki tej obserwacji możemy napisać nasz krok łączenia, usunąć wszystkie niedominowane punkty w lewej połowie, które mają współrzędną y mniejszą niż najwyższa współrzędna y punktu w niedominowanym zbiorze po prawej stronie pół. Mamy zestaw niedominowanych punktów.

Algorytm:

Find the median along x axis - O(n) time 
Find non-dominated points in the right half - T(n/2) 
Find non-dominated points in the right half - T(n/2) 
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points 

Równanie czasu:

T(n) = 2T(n/2) + O(n) which is O(n*logn) 

Można to poprawić dodatkowo O (N * logH), w którym H oznacza liczbę nie zdominowanych punktów , wymaga więcej wglądu w problem i jest dobrym rozszerzeniem, nad którym możesz popracować.