Zaawansowane algorytmy i struktury danych/Wykład 12

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 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 i będą dwoma odcinakami. Powiemy, że są one porównywalne w jeżeli miotła umieszczona w przecina je obydwa. Mówimy, że jest powyżej w , i oznaczamy , jeżeli i są porównywalne w oraz przecięcie z miotłą w jest wyżej niż przecięcie z z tą miotłą.

Ćwiczenie

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


Ćwiczenie

Pokaż jak sprawdzić, używając technik z poprzedniego wykładu, czy dla dwóch porównywalnych nie przecinających się odcinków i zachodzi ?

Dla każdego porządek jest porządkiem całkowitym na odcinkach przecinających miotłę w . Jednak porządek ten może być różny dla różnych 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 i musi istnieć takie położenie miotły , dla którego i będą kolejne w porządku . 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 , pozwalającej na wykonanie następujących operacji:

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

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

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


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

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

Twierdzenie 1

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

Dowód

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

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

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

Algorytm ten działa w czasie gdyż na jego czas działania składa się:

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

Najmniej odległa para punktów

Będziemy się teraz zajmować problemem znalezienia najmniej odległej pary punktów w zbiorze , gdzie . Interesować nas tutaj będzie odległość euklidesowa, którą dla punktów , oznaczamy przez , oraz definiujemy jako:

Dwa punkty w zbiorze mogą mieć te same współrzędne. W takim przypadku odległość między nimi wynosi . 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 parami punktów, możemy ten problem rozwiązać w czasie . Pokażemy teraz, jak wykorzystując technikę dziel i zwyciężaj problem ten można rozwiązać w czasie .

Algorytm

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

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


 NAJMNIEJ-ODLEGŁA-PARA
 1  if  then return 
 2  if  then return 
 3  korzystając z tablicy  znajdź pionową prostą  taką, że po jej lewej i
    prawej stronie jest  punktów
 4  niech   i  to będą punkty odpowiednio po lewej i prawej stronie 
 5  wyznacz tablice  oraz 
 6  NAJMNIEJ-ODLEGŁA-PARA
 7  NAJMNIEJ-ODLEGŁA-PARA
 8  
 9  niech  będzie tablicą  po usunięciu z niej punktów odległych od  o więcej niż 
 10 for  to  do
 11   for  to  do
 12     if  then 
 13 return 

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 , otrzymujemy równanie rekurencyjne na czas działania w postaci

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

Twierdzenie 2

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

Dowód

Jeżeli najmniej odległa para punktów znajduje się w zbiorze bądź , 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 i . Oznaczmy, tak jak w algorytmie, przez najmniejszą z odległości i . Widzimy teraz, że aby odległość między i mogła być mniejsza niż , punkty te nie mogą być bardziej odległe od niż o . W związku z tym usunięcie bardziej odległych punktów z w linii 9 algorytmu nie zmieni wyniku.

Rozważmy teraz prostokąt rozmiaru ułożony centralnie na linii . W prostokącie tym może znajdować się co najwyżej punktów z i , gdyż odległość między nimi jest co najmniej . 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ż . Dlatego też w linii 11 algorytmu możemy ograniczyć się do przejrzenia tylko 7 kolejnych punktów. End of proof.gif