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

<flash>file=Zasd_ilustr_k.swf|width=600|height=300</flash>

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|\geq 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. <flash>file=Zasd_ilustr_g.swf|width=600|height=300</flash>

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

<flash>file=Zasd_ilustr_g_stat.swf