Zaawansowane algorytmy i struktury danych/Wykład 12

Abstrakt

W ramach tego wykładu przedstawimy dwa algorytmy obrazujące wykorzystanie dwóch technik konstrukcji algorytmów geometrycznych. Do konstrukcji algorytmu sprawdzającego, czy w zbiorze odcinków istnieją dwa przecinające się, użyjemy techniki zamiatania. Natomiast do konstrukcji algorytmu wyznaczającego najmniejszą odległość w zbiorze punktów użyjemy techniki dziel i zwyciężaj.

Przecinanie się zbioru odcinków

Problem jaki nas będzie interesował, to problem przecinania się zbioru odcinków, w którym mamy za zadanie sprawdzić, czy w danym zbiorze odcinków $S$ istnieją dwa odcinki, które się przecinają. Wykorzystamy tutaj algorytm sprawdzania, czy para odcinków się przecina zaprezentowany na poprzednim wykładzie (zobacz).

W celu uproszczenia prezentacji idei algorytmu poczynimy dwa upraszczające założenia. Po pierwsze załóżmy, że żaden z odcinków nie jest pionowy. Po drugie załóżmy, że żadne trzy odcinki nie przecinają się w jednym punkcie. Algorytm ten może być prosto zmieniony, tak aby działał bez tych założeń. Zadanie 1 i Zadanie 2 do tego wykładu polega na pokazaniu tej modyfikacji. Jednak nie zawsze jest tak prosto. Bardzo często największym kłopotem w dowiedzeniu poprawności działania algorytmu geometrycznego jest poradzenie sobie ze wszystkimi szczególnymi i brzegowymi przypadkami.

Ponieważ założyliśmy, że w zbiorze nie ma odcinków pionowych, to każdy z odcinków może przecinać miotłę w co najwyżej jednym punkcie. Dlatego dla każdego położenia miotły możemy uporządkować odcinki przecinające ją zgodnie z kolejnością przecięć. Niech $s_1$ i $s_2$ będą dwoma odcinakami. Powiemy, że są one porównywalne w $a$ jeżeli miotła umieszczona w $x=a$ przecina je obydwa. Mówimy, że $s_1$ jest powyżej $s_2$ w $a$, i oznaczamy $s_1{>}_a{s}_2$, jeżeli $s_1$ i $s_2$ są porównywalne w $a$ oraz przecięcie $s_1$ z miotłą w $x=a$ jest wyżej niż przecięcie z $s_2$ z tą miotłą.

Ćwiczenie

Pokaż jak sprawdzić, używając technik z poprzedniego wykładu, czy dwa odcinki $s_1$ i $s_2$ są porównywalne w $a$?

Wystarczy sprawdzić, czy odcinki te przekraczają dowolny odcinek współliniowy z prostą $x=a$, np. odcinek $(a,0)-(a,1)$.

Ćwiczenie

Pokaż jak sprawdzić, używając technik z poprzedniego wykładu, czy dla dwóch porównywalnych nie przecinających się odcinków $s_1$ i $s_2$ zachodzi $s_1{<}_a{s}_2$?

Jeżeli odcinki się nie przecinają, to jeden z nich leży cały po jednej stronie prostej współliniowej z drugim odcinkiem. Wystarczy więc sprawdzić, czy jest to po stronie prawej.

Dla każdego $a$ porządek ${<}_a$ jest porządkiem całkowitym na odcinkach przecinających miotłę w $x=a$. Jednak porządek ten może być różny dla różnych $a$ ponieważ:

• dla różnych położeń miotły różne odcinki ją przecinają,
• jeżeli odcinki się przecinają, to ich kolejność po obydwu stronach przecięcia jest różna.

Co więcej, ponieważ zakładamy, że żadne trzy odcinki nie przecinają się w tym samym punkcie, to dla każdej pary przecinających się odcinków $e$ i $f$ musi istnieć takie położenie miotły $a$, dla którego $e$ i $f$ będą kolejne w porządku ${<}_a$. Tę własność właśnie wykorzystamy w algorytmie, który za chwilę skonstruujemy.

Algorytm

Będziemy przechowywać informację o porządku na odcinkach aktualnie przecinających miotłę w strukturze $T$, pozwalającej na wykonanie następujących operacji:

• WSTAW$(T,s)$ - wstawia odcinek $s$ do porządku $T$,
• USUŃ$(T,s)$ - usuwa odcinek $s$ z porządku $T$,
• POPRZEDNI$(T,s)$ - zwraca odcinek przed $s$ w porządku $T$,
• NASTĘPNY$(T,s)$ - zwraca odcinek po $s$ w porządku $T$.

Jeżeli zaimplementujemy tę strukturę z użyciem zrównoważonych drzew wyszukiwania, to operacje te będziemy mogli zrealizować w czasie $O(\log n)$, gdzie $n$ to całkowita liczba odcinków. Poniższy algorytm zwraca $TRUE$ wtedy i tylko wtedy, gdy zbiór $S$ przekazany jako argument zawiera parę przecinających się odcinków.

Algorytm sprawdza, w zbiorze $S$ istnieją dwa przecinające się odcinki

---

 ZBIÓR-ODCINKÓW-SIĘ-PRZECINA$(S)$
 1  $T=0$
 2  niech $P$ będzie posortowanym zbiorem końców odcinków z $S$ od lewej do prawej
 3  foreach $p\in P$ do
 4  begin
 5    if $p$ to lewy koniec odcinka $s$ then
 6    begin
 7      WSTAW$(T,s)$
 8      $s_p=$POPRZEDNI$(T,s)$
 9      $s_n=$NASTĘPNY$(T,s)$
 10     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_p \neq NIL \mbox{ \bf i }}
ODCINKI-SIĘ-PRZECINAJĄ$(s,s_p)$ then return $TRUE$
 11     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_n \neq NIL \mbox{ \bf i }}
ODCINKI-SIĘ-PRZECINAJĄ$(s,s_n)$ then return $TRUE$
 12   end
 13   if $p$ to prawy koniec odcinka $s$ then
 14   begin
 15      $s_p=$POPRZEDNI$(T,s)$
 16      $s_n=$NASTĘPNY$(T,s)$
 17     if Parser nie mógł rozpoznać (błąd składni): {\displaystyle s_p \neq NIL \mbox{ \bf i } s_n \neq NIL \mbox{ \bf i }}
 ODCINKI-SIĘ-PRZECINAJĄ$(s_p,s_n)$ then return $TRUE$
 18     USUŃ$(T,s)$
 19   end
 20  end
 21  return $FALSE$

Następująca animacja przedstawia działania tego algorytmu.

Plik:Zasd ilustr k.svg

Twierdzenie 1

Algorytm ZBIÓR-ODCINKÓW-SIĘ-PRZECINA zwraca $TRUE$ wtedy i tylko wtedy, gdy w $S$ istnieje para przecinających się odcinków.

Dowód

Algorytm ZBIÓR-ODCINKÓW-SIĘ-PRZECINA zwraca $TRUE$ w wypadku, gdy znalazł parę przecinających się odcinków. W celu pokazania jego poprawności wystarczy więc pokazać, że jeżeli w $S$ istnieje para przecinających się odcinków, to algorytm zwróci $TRUE$.

Załóżmy, że w $S$ jest co najmniej jedno przecięcie. Niech $p$ będzie tym najbardziej na lewo spośród nich. Niech $a$ i $b$ będą odcinkami przecinającymi się w $p$. Ponieważ po lewej stronie $p$ nie ma żadnych przecięć, to porządek przechowywany w $T$ jest poprawny do momentu przekroczenia $p$. Jak zauważyliśmy poprzednio, istnieje takie położenie $x$ miotły, dla którego $a$ i $b$ są kolejne w porządku ${<}_x$. Co więcej, istnieje takie $x$, że miotła w $x$ jest na lewo od $p$. Takie $x$ istnieje, ponieważ założyliśmy, że trzy odcinki nie przecinają się w jednym punkcie. W takim razie widzimy, że w $x$ porządek w $T$ poprawnie reprezentuje porządek ${<}_x$. Odcinki $a$ i $b$ mogły się stać kolejne w $T$:

• po wstawieniu jednego z nich do $T$, taka sytuacja będzie wykryta w liniach 8-11,
• po usunięciu odcinka między nimi, taką sytuację wykryjemy w liniach 15-17.

Algorytm ten działa w czasie $O(n\log n)$ gdyż na jego czas działania składa się:

• wykonanie linii 2 w czasie $O(n\log n)$,
• wykonanie pętli foreach w liniach 4-20 w całkowitym czasie $O(n\log n)$ - w każdym obrocie pętli wywoływana jest stała liczba operacji na strukturze $T$.

Najmniej odległa para punktów

Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze $Q$, gdzie $|Q|\ge 2$. Interesować nas tutaj będzie odległość euklidesowa, którą dla punktów $p=(x_p,y_p)$, $q=(x_q,y_q)$ oznaczamy przez $|p-q|$, oraz definiujemy jako:

$|p-q|=\sqrt{(x_p-x_q{)}^2+(y_p-y_q{)}^2}$

Dwa punkty w zbiorze $Q$ mogą mieć te same współrzędne. W takim przypadku odległość między nimi wynosi $0$. Informacja o najbliższej parze punktów może być przydatna w wypadku, gdy chcemy wykrywać kolizję między obiektami np. w systemach kontroli ruchu. Wyznaczając wszystkie odległości między $\left(\begin{array}{c}|Q|\\ 2\end{array}\right)$ parami punktów, możemy ten problem rozwiązać w czasie $O(n^2)$. Pokażemy teraz, jak wykorzystując technikę dziel i zwyciężaj problem ten można rozwiązać w czasie $O(n\log n)$.

Algorytm

W celu uniknięcia wielokrotnego sortowania punktów w wywołaniach rekurencyjnych, wykorzystamy dwie tablice $X$ i $Y$, które zawierały będą wszystkie punkty z $Q$ posortowane odpowiednio po $x$'owej współrzędnej i $y$'owej współrzędnej. Jeżeli podzielimy zbiór $Q$ na dwie części: $Q_L$ i $Q_R$, to odpowiednie tablice $X_L,Y_L$ i $X_R,Y_R$, zawierające posortowane elementy z $Q_L$ i $Q_R$ można wyznaczyć w czasie $O(|Q|)$. Musimy po prostu, przeglądając tablicę $X$ oraz $Y$, kopiować elementy w napotkanej kolejności do mniejszych tablic.

Algorytm znajduje najmniejszą odległość między parą punktów w $Q$

---

 NAJMNIEJ-ODLEGŁA-PARA$(Q,X,Y)$
 1  if $|Q|=2$ then return $\mathrm{\infty }$
 2  if $|Q|=2$ then return $|Q[1]-Q[2]|$
 3  korzystając z tablicy $X$ znajdź pionową prostą $l$ taką, że po jej lewej i
    prawej stronie jest $\lfloor \frac{|Q|}{2}\rfloor$ punktów
 4  niech $Q_L$  i $Q_P$ to będą punkty odpowiednio po lewej i prawej stronie $l$
 5  wyznacz tablice $X_L,X_P$ oraz $Y_L,Y_P$
 6  $d_L=$NAJMNIEJ-ODLEGŁA-PARA$(Q_L,X_L,Y_L)$
 7  $d_R=$NAJMNIEJ-ODLEGŁA-PARA$(Q_R,X_R,Y_R)$
 8  $d=\min (d_L,d_R)$
 9  niech $Y^{\prime }$ będzie tablicą $Y$ po usunięciu z niej punktów odległych od $l$ o więcej niż $d$
 10 for $i=1$ to $|Y^{\prime }|$ do
 11   for $j=1$ to $\min (7,|Y^{\prime }|-i)$ do
 12     if $|P[i]-P[i+j]|<d$ then $d=|P[i]-P[i+j]|$
 13 return $d$

Działanie tej procedury przedstawione jest na poniższej animacji.

Plik:Zasd ilustr g.svg

Nie wliczając wywołań rekurencyjnych, procedura ta działa w czasie liniowym. Zakładając, że $|Q|=n$, otrzymujemy równanie rekurencyjne na czas działania w postaci

$T(n)=\{\begin{array}{ll}2T(\frac{n}{2})+O(n)& \text{jeżeli }n>2,\\ O(1)& \text{jeżeli }n\le 2.\end{array}$

którego rozwiązaniem jest $T(n)=O(n\log n)$. Zauważmy, że czas potrzebny na posortowanie po raz pierwszy tablic $X$ i $Y$ także wynosi $O(n\log n)$. Całkowity czas potrzebny na znalezienie najmniejszej odległości między parą punktów w $n$-elementowym zbiorze wynosi więc $O(n\log n)$.

Twierdzenie 2

Algorytm NAJMNIEJ-ODLEGŁA-PARA wyznacza najmniejszą odległość między parą punktów w $Q$.

Dowód

Jeżeli najmniej odległa para punktów znajduje się w zbiorze $Q_L$ bądź $Q_P$, to zostanie ona znaleziona w wywołaniu rekurencyjnym. W takim razie musimy rozważyć tylko przypadek, w którym najmniej odległa para punktów to $p_L\in Q_L$ i $p_R\in Q_R$. Oznaczmy, tak jak w algorytmie, przez $d$ najmniejszą z odległości $d_L$ i $d_R$. Widzimy teraz, że aby odległość między $p_L$ i $p_R$ mogła być mniejsza niż $d$, punkty te nie mogą być bardziej odległe od $l$ niż o $d$. W związku z tym usunięcie bardziej odległych punktów z $Y$ w linii 9 algorytmu nie zmieni wyniku.

Rozważmy teraz prostokąt rozmiaru $2d\times d$ ułożony centralnie na linii $l$. W prostokącie tym może znajdować się co najwyżej $8$ punktów z $Q_L$ i $Q_R$, gdyż odległość między nimi jest co najmniej $d$. Zauważmy, że punktów mieszczących się w tym prostokącie znajdujących się poniżej danego punktu jest co najwyżej 7 (zobacz rysunek poniżej).

Plik:Zasd ilustr g stat.svg

Gdyby było ich więcej, odległość między nimi musiałaby być mniejsza niż $d$. Dlatego też w linii 11 algorytmu możemy ograniczyć się do przejrzenia tylko 7 kolejnych punktów.