Zaawansowane algorytmy i struktury danych/Ćwiczenia 12

From Studia Informatyczne

Zadanie 1

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy trzy lub więcej odcinków przecina się w tym samym punkcie.

Rozwiązanie

Rozumowanie w takim przypadku jest analogiczne do rozumowania przeprowadzonego na wykładzie. Niech p będzie punktem przecięcia najbardziej na lewo oraz niech będzie to punkt przecięcia k odcinków. Zauważmy, że istnieje takie położenie miotły x, że te k odcinków będzie występowało kolejno w porządku <_x. Zauważmy, że każda para tych punktów się przecina, a więc w momencie, w którym umieszczone one zostały na miotle w tej kolejności wykryte zostało ich przecięcie.

Zadanie 2

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy obecne są pionowe odcinki, a ich dolne końce traktujemy jako lewe końce, a górne końce jako prawe. Położenie odcinków w porządku na miotle wyznaczamy na podstawie współrzędnej y dolnego końca.

Rozwiązanie

Zauważ, że przy takim traktowaniu końcy odcinków pionowych w trakcie działania procedury zostanie sprawdzone, czy odcinek przecina się z z najniższym odcinkiem leżącym ponad dolnym końcem. Taki test wystarczy do sprawdzenia czy odcinek pionowy przecina się z jakimkolwiek innym odcinkiem. Zostanie tez sprawdzone, czy odcinek przecina się z najwyższym odcinkiem leżącym poniżej dolnego końca, a to wystarczy do przetestowania przecinania się odcinków pionowych między sobą.

Zadanie 3

Masz dane dwa zbiory n punktów P = \{p_1,\ldots,p_n\} oraz Q=\{q_1,\ldots,q_n\}. Zakładamy, że w sumie tych zbiorów nie ma trzech współliniowych punktów. Pokaż, że można dobrać w pary punkty P do punktów w Q tak aby utworzone w ten sposób odcinki się nie przecinały. Zaproponuj algorytm wyznaczający takie parowanie.

Rozwiązanie

Pokażemy teraz że istnieje taka para (p,q), że po obydwu stronach prostej p-q występuje tyle samo punktów ze zbioru P co ze zbioru Q. Wybierzmy dowolny punkt p \in P i posortujmy pozostałe punkty z P \cup Q po współrzędnych polarnych względem tego punktu. Oznaczmy ten posortowany ciąg przez s_1,\ldots,s_{2n}. Oznaczmy przez t_i różnicę między liczbą punktów z P występujących po jednej ze stron prostej p-s_i oraz liczbą punktów z Q występujących po tej samej stronie prostek p-s_i. Zauważmy, że |t_i - t_{i+1}| \le 1, ponieważ przy zmianie prostej co najwyżej jeden punkt zmienia stronę. Zauważmy, że z tej dyskretnej równości wynika, że dla pewnego i musi zachodzić t_i =0. Takie i możemy znaleźć w czasie O(n\log n). Mając taką prostą możemy rozbić problem na dwa mniejsze problemy. Ponieważ zagłębień tek rekursji będzie co najwyżej O(n), to algorytm wyznaczania parowania punktów z P do punktów z Q działać będzie w czasie O(n^2 \log n).