Zaawansowane algorytmy i struktury danych/Wykład 12

From Studia Informatyczne

Spis treści

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 s_p \neq NIL \mbox{ \bf i } ODCINKI-SIĘ-PRZECINAJĄ(s,s_p) then return TRUE
 11     if 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 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.



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. image:End_of_proof.gif

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{matrix}|Q|\\2\end{matrix}\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 \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' 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'| do
 11   for j=1 to \min(7,|Y'|-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.



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{cases} 2 T(\frac{n}{2}) + O(n) & \mbox{jeżeli } n>2,\\ O(1) & \mbox{jeżeli } n \le 2. \end{cases}

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).



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. image:End_of_proof.gif