Zaawansowane algorytmy i struktury danych/Ćwiczenia 12

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,\dots ,p_n\}$ oraz $Q=\{q_1,\dots ,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,\dots ,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)$.