\documentclass[11pt, times, a4paper, oneside]{article}

% kodowanie, polskie znaki
\usepackage[utf8]{inputenc}   % latin2, utf8 lub cp1250
\usepackage[polish]{babel}
\usepackage[T1]{fontenc}      % używaj rodziny EC


% strony i czcionki
\usepackage[margin=2.5cm]{geometry}
\usepackage{ulem}             % \uline - single underline
                              % \uuline - Double underline
                              % \uwave - Wavy underline
                              % \sout - Line through text
                              % \xout - Text marked over with slashes
\usepackage{algorithmic}

\usepackage{enumerate}        % dodatkowe sposoby numeracji, np. i, I, a, A
\setcounter{secnumdepth}{2}   % 2 - numeruj sekcje i subsekcje.
                              % 0 - nie numeruj nic, 5-wszystko

\newtheorem{remark}{\textsc{Uwaga}}[section]              % uwaga
\newtheorem{theorem}{Twierdzenie}                % twierdzenie
\newtheorem{defn}{Definicja}                     % definicja
\newtheorem{proof}{Dowód}                     % dowód

%\usepackage{indentfirst}      % wcinaj pierwszy akapit
%\setlength\parindent{1cm}     % rozmiar wcięcia
\renewcommand{\arraystretch}{1.4}  % wielkość komórki (współczynnik, 1=100%)

%% pomocne komendy
\usepackage{color}
\newcommand{\rysunek}{{\Large{\textsc{\textbf{\textcolor{red}{rysunek}}}}}}  % napis ĆWICZENIA
\newcommand{\quot}[1]{,,#1''}
%%


% odnośniki/hiperłącza
\usepackage{hyperref}
\usepackage{graphicx}
\hypersetup{
  colorlinks=true,
  citecolor=black, filecolor=black, linkcolor=black, urlcolor=black,
  pdfauthor=Rybicki,
  pdfcreator=kile,
  pdftitle=Drzewa Obszarów.}

\renewcommand{\b}[1] {\textbf{#1}}   % pogrubienie
\renewcommand{\i}[1] {\textit{#1}}   % kursywa
\renewcommand{\u}[1] {\uline{#1}}    % podkreślenie
\newcommand{\sans}[1] {\textsf{#1}}  % bezszeryfowa
\newcommand{\mono}[1] {\texttt{#1}}  % stałej szerokości

% informacje o dokumencie
\title{Drzewa Obszarów}
\author{
  Bartosz Rybicki\thanks{\texttt{rybicki.bartek(at)gmail.com}\quad numer
    albumu:~209096} }
\date{Wrocław, \today}

\begin{document}

\maketitle

\begin{abstract}
Drzewa obszarów to struktura wykorzystywana do zadawania zapytań o punkty w obszarze ortogonalnym. O punktach można
myśleć jak o rekordach w bazie danych. Praca zawiera opis struktury oraz algorytmu przy pomocy którego można tą strukturę zbudować. Opisany jest również sposób zadania zapytań o zbiór punktów. Wszystkie opisane algorytmy są analizowane zarówno jeśli chodzi o złożoność czasową jak i o pamięciową.
\end{abstract}

\thispagestyle{empty}        % pierwsza strona bez numeru
%\tableofcontents             % wygeneruj spis treści

\section{Opis problemu i jego motywacja na przykładzie zadawania zapytań bazie danych}
Wyobraźmy sobie, że chcemy uzyskać informacje o pracownikach naszej firmy, którzy zarabiają miedzy 3000 a 4000 tysiące złotych oraz urodzili się miedzy 1950 a 1955 rokiem. Każdy pracownik może zostać opisany jako para informacji (pensja, rok urodzenia). Można o tym myśleć jak o punkcie w przestrzeni $R^2$. Przykładowy wynik zapytania: \\
\begin{center}
\includegraphics[width=100mm]{113.png} \\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

\begin{remark}
Zauważmy, że na każdy rekord zawierający d pól możemy patrzeć jak na punkt w przestrzeni $R^d$. Zatem od teraz nie będziemy myśleć o rekordach w bazie, ale o punktach w przestrzeni $R^d$.
\end{remark}

\section{Przeszukiwanie obszarów jednowymiarowych}
Załóżmy, że mamy zbiór punktów na osi OX i interesują nas te należące do przedziału $[x, x']$. Dla zadanego zbioru punktów możemy zbudować zrównoważone drzewo wyszukiwań binarnych i przy jego pomocy odpowiadać na zapytania o punkty z danego odcinka. Załóżmy, że mamy następujący zbiór punktów: $\{3, 10, 19, 23, 30, 37, 49, 59, 62, 70, 80, 100, 105\}$ i chcemy odpowiedzieć na pytanie o punkty leżące w przedziale $[18,77]$. \\
\begin{center}
\includegraphics[width=100mm]{115.png} \\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

\subsection{Algorytm budowy drzewa}
Alg(P)
\begin{algorithmic}[1]
\IF{|P| == 1}
    \STATE stwórz liść pamiętający jeden punkt
\ELSE
    \STATE $v_{value}$ := mediana($P_{x}$);
    \STATE podziel P na zbiory: $P_{x \leq mediana}$, $P_{mediana < x}$;
    \STATE $v_{lewy}$ := Alg($P_{\leq x}$);
    \STATE $v_{prawy}$ := Alg($P_{x <}$);
\ENDIF
\STATE return v;
\end{algorithmic}

\begin{theorem}
 Czas budowy struktury to $O(n log n)$ a wymagana pamięć to $O(n)$.
\end{theorem}

\begin{proof}
Czas: $T(n) = 2 * T(\frac{n}{2}) + O(n) = O(n log n)$ - szukamy mediany oraz dwukrotnie wywołujemy się dla zbioru o połowę mniejszego. \\
Pamięć: $M(n) = 2 * M(\frac{n}{2}) + O(1) = O(n)$ - korzeń zajmuje pamięć rzędu O(1). Inny sposób myślenia o koszcie pamięciowym tej struktury to liczenie kosztu ``od dołu`` najniższy poziom wymaga n komórek pamięci, kolejny $\frac{n}{2}$ itd. Zatem $M(n) = n + \frac{n}{2} + \frac{n}{4} + ... + \frac{n}{2^{log n}} = O(n)$
\end{proof}

\begin{remark}
Zauważmy, że dla posortowanego zbioru czas budowy struktury to $O(n)$. Dzieje się tak ponieważ szukanie mediany odbywa się w czasie stałym. Można też budować drzewo od dołu i nie przejmować się problemem mediany.
\end{remark}

\begin{defn}
Wierzchołek dzielący dla przedziału [x, x'] to taki w którym rozchodzą się ścieżki od korzenia do x oraz x'.
\end{defn}
\newpage
\subsection{Algorytm zapytania o przedział}
Alg(T, [x,x'])
\begin{algorithmic}[1]
  \STATE schodź w dół drzewa do czasu aż znajdziesz wierzchołek dzielący lub dojdziesz do liścia;
  \IF {$v_{dziel}$ jest liściem} 
    \STATE sprawdź czy $v_{dziel}$ należy do przedziału i ewentualnie dodaj go do wyniku;
  \ELSE
    \STATE zejdź ścieżką od x i dodaj do wyniku punkty wiszące w liściach drzew na prawo od ścieżki sprawdź czy punkt pamiętany w liściu (na końcu ścieżki do x) należy do przedziału, jeśli tak to dodaj go do wyniku;
    \STATE zejdź ścieżką od x' i dodaj do wyniku punkty wiszące w liściach drzew na lewo od ścieżki sprawdź czy punkt pamiętany w liściu (na końcu ścieżki do x) należy do przedziału, jeśli tak to dodaj go do wyniku;
  \ENDIF
  \STATE return wynik;
\end{algorithmic}

\begin{theorem}
 Czas wykonania zapytania to O(log n + k), gdzie k to rozmiar wyniku, tj. liczba punktów składających się na wynik.
\end{theorem}

\begin{proof}
 Zejście w drzewie do x oraz x' to O(log n), bo drzewo jest zrównoważone. Koszt przejścia odpowiednich poddrzew jest liniowy od liczby ich liści i wynosi O(k). Zatem całkowity czas potrzebny na wykonanie zapytania oraz obliczenie wyniku to O(log n + k)
\end{proof}

\section{Drzewa obszarów (2D)}

\begin{remark}
 Tymczasowo załóżmy, że żadne dwa punkty nie mają takich samych współrzędnych x oraz y. Potem pokażemy jak pozbyć się tego (nierealnego) założenia.
\end{remark}

\begin{defn}
 Podzbiór punktów pamiętanych w liściach poddrzewa zakorzenionego w węźle v nazywamy podzbiorem kanonicznym v oraz oznaczamy jako P(v).
\end{defn}

\subsection{Opis struktury}
\begin{itemize}
 \item Główne drzewo T jest zrównoważonym drzem wyszukiwań binarnych (BST) zbudowanym względem współrzędnych x punktów ze zbioru P
 \item Dla każdego węzła wewnętrznego lub liścia v w drzewie T, podzbiór kanoniczny P(v) jest pamiętany w zrównoważonym drzewie wyszukiwań binarnych $T_{stow}(v)$ względem współrzędnej y punktów. Węzeł v pamięta wskaźnik do drzewa $T_{stow}(v)$, które nazywamy strukturą stowarzyszoną z v.
\end{itemize}

\begin{center}
\includegraphics[width=100mm]{127.png} \\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

\subsection{Algorytm budowy struktury}
\begin{itemize}
 \item $P$ - zbiór punktów
 \item $P_{x}$ - zbiór P posortowany po współrzędnej x
 \item $P_{y}$ - zbiór P posortowany po współrzędnej y
\end{itemize}
Alg($P_{x}$, $P_{y}$)
\begin{algorithmic}[1]
  \IF{(|P| == 1)}
    \STATE stwórz liść pamiętający jeden punkt i zbuduj $T_{stow}$ dla tego punktu;
  \ELSE
    \STATE $v_{value}$ := mediana($P_{x}$);
    \STATE podziel $P_{x}$ oraz $P_{y}$ na zbiory: $P_{x}^{x \leq v_{value}}$, $P_{x}^{v_{value} < x}$ $P_{y}^{x \leq v_{value}}$ oraz $P_{y}^{v_{value} < x}$;
    \STATE $v_{lewy}$ := Alg($P_{x}^{x \leq v_{value}}$, $P_{y}^{x \leq v_{value}}$);
    \STATE $v_{prawy}$ := Alg($P_{x}^{v_{value} < x}$, $P_{y}^{v_{value} < x}$);
    \STATE $v_{stow}$ := zbuduj $T_{stow}(P_{y})$;
  \ENDIF
  \STATE return v;
\end{algorithmic}

\begin{theorem}
 Zarówno czas jak i pamięć potrzebna do budowy struktury to $O(n log n)$.
\end{theorem}

\begin{proof}
Czas: $T(n) = 2 * T(\frac{n}{2}) + O(n) = O(n log n)$ - szukamy mediany oraz dwukrotnie wywołujemy się dla zbioru o połowę mniejszego. Czas potrzebny na zbudowanie struktury stowarzyszonej jet liniowy, bo zbiór $P_{y}$ jest odpowiednio posortowany.  \\
Pamięć: Każdy punkt p jest pamiętany w strukturze stowarzyszonej węzłów na ścieżce w T ku liściowi zawierającemu p. Ścieżka ma długość $O(log n)$ a wszystkich punktów jest $O(n)$ zatem cała struktura zajmuje $O(nlogn)$ komórek pamięci.
\end{proof}

\subsection{Algorytm zapytania o zbiór punktów w obszarze $[x, x'] \times [y, y']$}
Alg(T, $[x, x']\times[y, y']$)
\begin{algorithmic}[1]
  \STATE $v_{dziel}$ := WierzchołekDzielący(T, [x, x']);
  \IF {$v_{dziel}$ jest liściem}
    \STATE sprawdź czy ma znajdować się w wyniku jeśli tak to dodaj go do rozwiązania;
  \ELSE
    \STATE idź ścieżką do x i wykonuj zapytania jednowymiarowe dla poddrzew na prawo od ścieżki, na końcu ścieżki sprawdź czy punkt w liściu ma być podany;
    \STATE idź ścieżką do x' i wykonuj zapytania jednowymiarowe dla poddrzew na lewo od ścieżki, na końcu ścieżki sprawdź czy punkt w liściu ma być podany;
  \ENDIF
  \STATE return wynik;
\end{algorithmic}

\begin{theorem}
 Czas zapytania o punkty z obszaru $[x, x'] \times [y, y']$ to $O(log^{2}n + k)$, gdzie k to rozmiar wyniku.
\end{theorem}

\begin{proof}
Każde zapytanie o obszar jednowymiarowy zajmuje czas rzędu $O(log n + k_{v})$ takich zapytań będzie $O(log n)$, natomiast liczba  zwróconych punktów to $\sum k_{v} = k$. Zatem czas całego zapytania zamyka się w $O(log^{2}n + k)$.
\end{proof}

\section{Uogólnienie drzew obszarów na wiele wymiarów}
Algorytm budowy struktury jest bardzo podobny do algorytmu dla drzew dwuwymiarowych. Podstawowa różnica w algorytmie to brak sortowania po współrzędnych. Struktury stowarzyszone dla drzew pierwszego poziomu to (d-1)-wymiarowe drzewa obszarów. Analogicznie dla drzew kolejnych poziomów.

\begin{theorem}
 Niech P będzie zbiorem n punktów w d-wymiarowej przestrzeni, gdzie d $\geq$ 2. Drzewo obszarów dla P używa $O(n log^{d-1} n)$ pamięci i można je zbudować w czasie $O(n log^{d-1} n)$. Punkty z P leżące w prostokątnym obszarze zapytania, można podać w czasie $O(log^{d} n + k)$, gdzie k jest rozmiarem wyniku.
\end{theorem}

\begin{proof}
Tworzenie d-wymiarowego drzewa obszarów polega na zbudowaniu zrównoważonego BST, co wymaga czasu $O(n logn)$, i konstruowaniu struktur stowarzyszonych. W węzłach na dowolnej głębokości drzewa pierwszego poziomu każdy punkt jest pamiętany w dokładnie jednej strukturze stowarzyszonej. Czas potrzebny na utworzenie struktur stowarzyszonych na pewnej głębokości można ograniczyć przez $O(T_{d-1}(n))$, jest tak ponieważ $T_{d-1}(n)$ jest conajmniej liniowe. Zatem całkowity czas potrzebny na utworzenie struktury można opisać następującym wzorem $$T_{d}(n) = O(nlogn) + O(logn) *  O(T_{d-1}(n)) = O(n log^{d-1} n)$$ jest tak ponieważ $T_{2}(n) = O(nlogn)$ - pokazaliśmy to przy okazji analizy drzew dwuwymiarowych.
Analizę zużywanej pamięci można przeprowadzić w analogiczny sposób z tą różnicą, że BST wymaga O(n) pamięci, zatem pamięć potrzebna do utworzenia struktury może zostać opisana następującym wzorem: $$M_{d}(n) = O(n) + O(logn) *  O(M_{d-1}(n)) = O(n log^{d-1} n)$$ jest tak ponieważ $M_{2}(n) = O(nlogn)$ - pokazaliśmy to przy okazji analizy drzew dwuwymiarowych. Oznaczmy przez $Q_{d}(n)$ czas potrzebny na wyznaczenie wszystkich drzew jednowymiarowych, które w swoich liściach przechowują wynik naszego zapytania. Wiemy, że $Q_{2}(n) = O(log^{2}n)$, zatem prawdziwy jest wzór $$Q_{d}(n) = O(log n) + O(log n) Q_{d-1}(n) = O(log^{d}n)$$ Zatem czas potrzebny na wykonanie zapytania oraz zwrócenie wyniku to $O(log^{d}n + k)$, gdzie k jest rozmiarem wyniku.
\end{proof}

\section{Kaskadowanie cząstkowe}
Omawialiśmy już strukturę która operowała na elementach z $R^2$ i odpowiadała na zapytania o obszar $[x,x']\times[y,y']$ w czasie $O(log^{2} n + k)$, teraz pokażemy jak zredukować ten czas do $O(log n + k)$. 

\subsection{Przykład}

Przedstawmy pomysł kaskadowania cząstkowego na prostym przykładzie. Niech $S_{2} \subseteq S_{1}$ oraz istnieją tablicę $A_{1}$, $A_{2}$, takie że $A_{1}$ przechowuje posortowane elementy z $S_{1}$, analogicznie dla $A_{2}$ oraz $S_{2}$. Jeśli $A_{1}[i]$ pamięta wartość $y_{i}$ to przechowujemy wskaźnik z $A_{1}[i]$ do pozycji w $A_{2}$ z najmniejszym kluczem większym lub równym niż $y_{i}$. Jeśli nie ma takich kluczy to wskaźnik na wartość NULL. Teraz gdy chcemy wypisać wszystkie elementy z $S_{1}$ oraz $S_{2}$, które należą do przedziału $[y_{1}, y_{2}]$ wystarczy nam jedno przeszukiwanie binarne w tablicy $A_{1}$ oraz przejście obu tablic co zajmuje czas $O(log n + k)$, gdzie k to liczba punktów z $S_{1}$ oraz $S_{2}$, które należą do przedziału $[y, y']$. Przykład zapytania dla przedziału $[20, 65]$ \\
\begin{center}
\includegraphics[width=100mm]{135.png} \\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

\subsection{Przeniesienie pomysłu na drzewa obszarów}

Struktura stowarzyszona dla konkretnego wierzchołka v w drzewie obszarów przestaje być zbalansowanym BST. Warto zamienić je na tablicę $A(v)$ punktów uporządkowanych względem współrzędnej y. Każdy element tablicy A(v) pamięta dwa wskaźniki do odpowiednich pozycji w $A(v_{lewy})$ oraz $A(v_{prawy})$. Przypuśćmy, że $A(v)[i]$ pamięta punkt $p = (p_{x}, p_{y})$, wtedy wskaźnik do $A(v_{lewy})$ pokazuje na pozycję najmniejszego elementu $p^{'} = (p^{'}_{x}, p^{'}_{y})$ dla którego zachodzi $p_{y} \leq p^{'}_{y}$. Analogicznie dla drugiego wskaźnika i tablicy $A(v_{prawy})$. \\
\begin{center}
\includegraphics[width=100mm]{136.png}\\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

W jaki sposób odpowiadamy na pytanie o obszar $[x, x'] \times [y,y']$? W tablicy stowarzyszonej wierzchołka dzielącego robimy wyszukiwanie binarne w celu znalezienia najmniejszego elementu większego lub równego y. Dalej procedura jest analogiczna jak wcześniej. Schodzimy ścieżką do wierzchołka x i wypisujemy poddrzewa, które leżą na prawo od ścieżki. W jaki sposób wypisujemy poddrzewa? Znamy wskaźnik do najmniejszego (względem współrzędnej y) elementu z tablicy stowarzyszonej (możemy ustalać odpowiednie pozycje w tablicach stowarzyszonych przechodząc drzewo), który spełnia nasze kryteria, zatem przechodzimy odpowiednią tablicę aż dojdziemy do ostatniego elementu, który jest $\leq y^{'}$.

\begin{theorem}
 Czas zapytania o obszar $[x,x']\times[y,y']$ wynosi O(log n + k)
\end{theorem}

\begin{proof}
 Jakie operacje wykonujemy? Wyszukiwanie binarne w tablicy stowarzyszonej z wierzchołkiem dzielącym, przejście od wierzchołka dzielącego do liści przechowujących x oraz x', wypisane odpowiednich elementów z tablic stowarzyszonych z wybranymi wierzchołkami. Czas wszystkich operacji zamyka się w $O(log n + k)$.
\end{proof}

\begin{remark}
Ta poprawka pozwala nam przyspieszyć wyszukiwanie punktów w przestrzeni $R^d$ z czasu $O(log^{d}n + k)$ do $O(log^{d-1}n + k)$ dla $d \geq 2$. W jaki sposób? Struktury jednowymiarowe zamieniamy na tablice stowarzyszone, a zapytanie dla struktury dwuwymiarowej wykonujemy tak jak to zostało opisane wyżej.
\end{remark}

\section{Ogólny zbiór punktów}
\subsection{Pozbycie się niewygodnego założenia}
Poczyniliśmy (nierealne) założenie o tym że żadne dwa punkty nie mają takiej samej współrzędnej x lub y. Teraz pokażemy jak pozbyć się tego niewygodnego założenia. Każdy punkt $p = (p_{x}, p_{y})$ będziemy reprezentować jako $\hat{p} = ((p_{x}|p_{y})$, $(p_{y}|p_{x}))$. Porządek na parach $(a|b)$ zadajemy w następujący sposób $$(a|b) < (\acute{a}|\acute{b}) \Leftrightarrow a < \acute{a} \vee (a = \acute{a} \wedge\and b < \acute{b})$$

\begin{remark}
 Jeśli punkty p oraz q są różne to $\hat{p}$ i $\hat{q}$ są różne na wszystkich współrzędnych.
\end{remark}

\subsection{Sposób zadawania zapytania}
Załóżmy, że chcemy zapytać o obszar $R = [x, x'] \times [y, y']$. W tym celu definiujemy obszar $\hat{R} = [(x| -\infty), (x'|+\infty)] \times [(y|-\infty), (y'|+\infty)]$ o który będziemy pytać algorytm. Pokażmy, że $p \in R \Leftrightarrow \hat{p} \in \hat{R}$ $$p = (p_{x}, p_{y}) \Rightarrow \hat{p} = ((p_{x}|p_{y}), (p_{y}|p_{x}))$$ $$p \in R \Leftrightarrow x \leq p_{x} \leq x' \wedge\and y \leq p_{y} \leq y'$$ $$\Updownarrow$$ $$(x, -\infty) \leq (p_{x}, p_{y}) \leq (x', +\infty) \wedge\and (y,-\infty) \leq (p_{y},p_{x}) \leq (y', +\infty)$$ $$\Updownarrow$$ $$\hat{p} \in \hat{R}$$

\begin{thebibliography}{9}
\bibitem{GejoBook} {Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{thebibliography}

\end{document}