\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{lemma}{Lemat}                % lemat
\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=Panasiuk,
  pdfcreator=kile,
  pdftitle=Drzewa Odcinkó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{Struktury do odpowiadania na zapytania o okienkowanie\\
Drzewa odcinków}
\author{Marcin Panasiuk}
\date{Wrocław, 22 listopada 2010}

\begin{document}

\maketitle


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

\section{Opis problemu}

W obecnych czasach wiele osób korzysta z systemu nawigacji drogowej GPS. Taki system przechowuje całą mapę drogową danego kraju i co jakiś czas musi szybko pokazywać zaledwie niewielki jej fragment. Takim fragmentem jest z reguły prostokątne okienko o bokach równoległych do osi. Zapytanie o taki obszar nazywa się zapytaniem o okienkowanie. \\
\begin{center}
\includegraphics[width=100mm]{1.png} \\
\small{Źródło: Geometria Obliczeniowa. Algorytmy i zastosowania, M. de Berg}
\end{center}

Mapa może być przechowywana w postaci odcinków, każdy odcinek reprezentuje mały element mapy (kawałek drogi, rzeki, granicy obszaru…). Sprawdzenie każdego pojedynczego odcinka, aby zobaczyć, czy leży on wewnątrz okienka, nie jest metodą nadającą się do pracy z ilością danych, z którymi mamy do czynienia. Zamiast tego będziemy pamiętać mapę w wyspecjalizowanych strukturach danych, umożliwiających szybkie odpowiedzi na zapytanie o okienkowanie.

\section{Drzewa obszarów}
Odcinki, które są odpowiedzią dla zapytania o okienkowanie, można podzielić na różne przypadki: odcinek może leżeć całkowicie w ramce zapytania, jednokrotnie przecinać brzeg ramki, przecinać dwa brzegi. W dwóch pierwszych przypadkach odcinek ma co najmniej jeden koniec wewnątrz ramki. Możemy znaleźć taki odcinek pytając o obszar ramki dla $2n$ końców odcinków z całej mapy. Do takich zapytań służy dwuwymiarowe drzewo obszarów. Struktura ta zużywa $O(n\log n)$ pamięci, czas jej utworzenia to $O(n\log n)$, a na zapytanie o obszar można odpowiedzieć w czasie $O(\log^2n +k)$, gdzie $k$ jest liczbą podawanych punktów. Dodatkowo, stosując kaskadowanie cząstkowe można zredukować czas zapytania do $O(\log n + k)$. Do znajdowania odcinków z ostatniego przypadku posłużymy się drzewem odcinków.


\section{Drzewa odcinków}

\subsection{Wstęp}
Odcinki, które podwójnie przecinają brzeg okienka, mogą być znalezione poprzez zapytanie o odcinki przecinające każdy z $4$ brzegów (oczywiście trzeba pamiętać, żeby nie podawać powtórzeń). Wystarczy, że od teraz zajmiemy się tylko problemem jak znaleźć odcinki przecinające pionowy brzeg ramki. Z poziomymi brzegami jest analogicznie. Przyjmijmy następujące oznaczenia: dany jest $n$-elementowy zbiór $S$ dowolnie zorientowanych odcinków na płaszczyźnie i chcemy znaleźć te odcinki z $S$, które przecinają pionowy odcinek zapytania $q = q_x \times [q_y, q’_y]$. Dodatkowo zakładamy, że odcinki nie mogą się przecinać, ale za to mogą się stykać końcami.\\
\indent Zanim otrzymamy pełne rozwiązanie, zajmijmy się najpierw problemem znajdowania odcinków, które przecinają pionową prostą zapytania $q_x$. Oznaczmy przedziały $x$-owe wszystkich odcinków poprzez zbiór $I = \{[x_1, x’_1], [x_2, x’_2], \ldots, [x_n, x’_n]\}$. Nasz problem wygląda teraz tak, że musimy znaleźć te odcinki ze zbioru $I$, które zawierają punkt $q_x$. 


\subsection{Opis drzewa odcinków}

Możemy podzielić prostą poziomą na przedziały elementarne utworzone przez końce odcinków ze zbioru I:
\begin{center}
$(-\infty, p_1), [p_1, p_1], (p_1, p_2), [p_2, p_2], \ldots, [p_m, p_m], (p_m, \infty)$
\end{center}

\indent Można zauważyć, że dla każdego punktu z danego przedziału elementarnego odpowiedź na zapytanie jest taka sama. Powodem, dla którego rozważamy przedziały otwarte na przemian z domkniętymi dla pojedynczych punktów jest to, że odpowiedź na zapytanie we wnętrzu przedziału elementarnego niekoniecznie jest taka sama jak na jego końcach.\\
\indent Aby znaleźć te przedziały z $I$, które zawierają punkt zapytania $q_x$, wystarczy znaleźć przedział elementarny, który zawiera $q_x$. W tym celu możemy zbudować zrównoważone drzewo binarne $T$, którego liście będą odpowiadały przedziałom elementarnym.\\
\indent Niech przedział elementarny  odpowiadający liściowi $u$ to będzie Int$(u)$. Jeśli w każdym liściu $u$ będziemy pamiętali te przedziały z $I$, które zawierają przedział elementarny Int$(u)$, to wystarczy już tylko znaleźć dany liść, co w drzewie binarnym trwa $O(\log n)$. Czas odpowiedzi na zapytanie wyniesie wtedy $O(\log n + k)$, gdzie $k$ to rozmiar wyniku, pamiętany w danym liściu. Jedyny problem to rozmiar pamięciowy naszej struktury. Rozważmy następujący przypadek:\\

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

Na rysunku widać, że każdy odcinek byłby pamiętany w około połowie przedziałów elementarnych, co prowadzi do wniosku, że pesymistyczny rozmiar pamięciowy struktury wyniósłby $O(n^2)$. Aby temu zaradzić, należy najpierw zauważyć, że przedziały można pamiętać nie tylko w liściach, ale również w węzłach wewnętrznych drzewa T. Rozważmy następujący przykład:

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

Przedział $s$ jest pamiętany w liściach $u_1, u_2, u_3, u_4$ i $u_5$. Kluczową obserwacją jest to, że  ścieżka przeszukiwań kończy się w jednym z liści $u_1$-$u_4$ wtw gdy przechodzi przez węzeł wewnętrzny $v$. Dlatego można zapamiętać przedział $s$ w węźle $v$ i liściu $u_5$ zamiast w liściach $u_1$-$u_5$. Generalnie możemy zapamiętywać dany przedział w pewnej liczbie węzłów, które pokrywają ten przedział i wybieramy te węzły tak wysoko jak to możliwe. Taka struktura to właśnie drzewo odcinków. Poniżej przestawione jest przykładowe drzewo odcinków:

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

Węzły wewnętrzne $T$ odpowiadają przedziałom, które są sumą przedziałów elementarnych. Przedział Int$(v)$, odpowiadający węzłowi $v$, jest sumą przedziałów elementarnych Int$(u)$ liści w poddrzewie zakorzenionym w $v$. Każdy węzeł lub liść w $T$ oprócz przedziału Int$(v)$ pamięta zbiór $I(v)$ tych przedziałów z $I$, które zawierają w sobie Int$(v)$, ale nie zawierają w całości Int(rodzic$(v)$) (bo pamiętamy przedziały w jak najwyższych węzłach).

\begin{lemma}
Drzewo odcinków dla zbioru $n$ przedziałów używa $O(n\log n)$ pamięci.
\end{lemma}

\begin{proof}
Lemat będzie udowodniony, jeżeli zostanie pokazane, że każdy przedział $s$ jest pamiętany w zbiorach $I(v)$ maksymalnie w dwóch węzłach na każdej wysokości drzewa. Niech $v_1, v_2$ i $v_3$ będą trzema węzłami na tej samej wysokości i niech przedział $s$ będzie pamiętany w $v_1$ i $v_3$.

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

Wiemy zatem, że $s$ obejmuje cały przedział od lewego końca Int$(v_1)$ do prawego końca Int$(v_3)$. Ponieważ $v_2$ leży między $v_1$ i $v_3$, Int(rodzic$(v2))$ musi być zawarty w $s$. Stąd $s$ nie będzie pamiętany w $v_2$.
\end{proof}

\subsection{Konstrukcja drzewa odcinków}

Otrzymanie przedziałów elementarnych sprowadza się do posortowania końców przedziałów z $I$. Przedziały elementarne stanowią liście drzewa, zatem konstrukcja zrównoważonego drzewa binarnego $T$ polega teraz na budowaniu węzłów od dołu do góry i dla każdego węzła drzewa $v$ należy określić reprezentujący go przedział Int$(v)$. Podejście takie zajmie liniowy czas. Pozostaje utworzyć dla każdego węzła zbiór odpowiedzi $I(v)$ w nim pamiętany. W tym celu pojedynczo wstawiamy przedziały do drzewa odcinków. Przedział jest wstawiany do $T$ poprzez wywołanie następującej procedury z $v = korzen(T)$.\\

\noindent $INSERT\_SEGMENT\_TREE(v, [x, x’])$\\
Dane wejściowe: Korzeń (poddrzewa) drzewa odcinków i przedział\\
Wynik: Przedział będzie zapisany w poddrzewie.
\begin{algorithmic}[1]
\IF{ Int$(v) \subseteq [x, x']$ }
	\STATE zapisz $[x, x']$ w $I(v)$
\ELSE
	\IF{ Int$(lewy(v)) \cap [x, x'] \neq \emptyset$ }
		\STATE $INSERT\_SEGMENT\_TREE(lewy(v), [x, x’])$
	\ENDIF
	\IF{ Int$(prawy(v)) \cap [x, x'] \neq \emptyset$ }
		\STATE $INSERT\_SEGMENT\_TREE(prawy(v), [x, x’])$
	\ENDIF
\ENDIF
\end{algorithmic}

\begin{lemma}
Wstawienie wszystkich przedziałów do drzewa odcinków zajmuje $O(n\log n)$ czasu.
\end{lemma}

\begin{proof}
Lemat zostanie udowodniony, jeśli pokażemy, że wstawienie pojedynczego przedziału zajmuje $O(\log n)$ czasu. W każdym węźle, który jest odwiedzany, spędzamy stały czas. Gdy odwiedzamy węzeł $v$, to albo zapamiętujemy $[x, x’]$ w $I(v)$, albo Int$(v)$ zawiera koniec $[x, x’]$. Ponieważ przedział jest pamiętany co najwyżej $2$ razy na każdym poziomie oraz jest co najwyżej jeden węzeł na każdym poziomie, któremu odpowiada przedział zawierający $x$ i analogicznie zawierający $x’$, to na każdym poziomie odwiedzamy maksymalnie $4$ węzły.
\end{proof}

\subsection{Zapytania w drzewie odcinków}

Poniższa funkcja znajduje przedziały zawierające punkt $q_x$. Początkowo jest wywoływana z $v = korzen(T)$.\\

\noindent $QUERY\_SEGMENT\_TREE(v, q_x)$\\
Dane wejściowe. Korzeń (poddrzewa) drzewa odcinków i punkt zapytania $q_x$.\\
Wynik. Wszystkie przedziały w drzewie zawierające $q_x$.
\begin{algorithmic}[1]
\STATE Podaj wszystkie przedziały w $I(v)$
\IF{ $v$ nie jest liściem }
	\IF{ $q_x \in $ Int$(lewy(v))$ }
		\STATE $QUERY\_SEGMENT\_TREE(lewy(v), q_x)$
	\ELSE
		\STATE $QUERY\_SEGMENT\_TREE(prawy(v), q_x)$
	\ENDIF
\ENDIF
\end{algorithmic}

\begin{lemma}
Przedziały zawierające punkt zapytania $q_x$ można podać w czasie $O(\log n + k)$, gdzie $k$ jest liczbą podawanych przedziałów
\end{lemma}

\begin{proof}
Algorytm zapytania odwiedza jeden węzeł na każdym poziomie drzewa, więc w sumie $O(\log n)$ węzłów. W węźle spędzamy $O(k_v)$ czasu, gdzie $k_v$ to liczba podawanych przedziałów w węźle $v$.
\end{proof}

\subsection{Przystosowanie drzewa odcinków do okienkowania}

Wróćmy do problemu okienkowania. Mamy już drzewo odcinków jako strukturę do znajdowania odcinków przecinających prostą zapytania $q_x$. Musimy ją delikatnie przerobić, żeby umieć znajdować odcinki przecinające pionowy odcinek zapytania $q = q_x \times [q_y, q’_y]$. Zauważmy, że teraz każdy węzeł $v$ odpowiada pionowej płycie Int$(v) \times (-\infty, \infty)$. Odcinki, które należą do $I(v)$ danego węzła, to te odcinki, które przecinają obie proste $x$ i $x’$, gdzie Int$(v) = [x, x’]$. Obrazuje to rysunek:

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

Teraz jeśli przypomnimy sobie o założeniu poczynionym na początku, że odcinki nie mogą się ze sobą przecinać, a jedynie stykać końcami, to łatwo zauważyć, że wszystkie odcinki w danej płycie $I(v)$ można uporządkować względem pionu. Możemy zatem zamiast samych $x$-przedziałów odcinków, trzymać całe odcinki w $I(v)$ uporządkowane względem pionu. Można to osiągnąć przyjmując, że $I(v)$ to zrównoważone drzewo binarne. Wtedy czas dodawania przedziałów odcinków do drzewa odcinków wzrośnie z $O(n\log n)$ do $O(n\log^2n)$ – w linijce $2$ algorytmu $INSERT\_SEGMENT\_TREE$ czas wstawiania rośnie ze stałego do logarytmicznego. Natomiast wyszukiwanie odcinków przecinających odcinek zapytania $q$ wyniesie $O(\log^2n + k)$, gdzie $k$ to liczba zwracanych odcinków – w linijce $1$ algorytmu $QUERY\_SEGMENT\_TREE$ czas ze stałego wzrośnie do logarytmicznego.

\subsection{Podsumowanie}
Dla zbioru $S$ składającego się z $n$ odcinków na płaszczyźnie z rozłącznymi wnętrzami, odcinki przecinające prostokątne, równoległe do osi okienko zapytania można podać w czasie $O(\log^2n + k)$ stosując strukturę danych, która używa $O(n\log n)$ pamięci, gdzie $k$ jest liczbą podawanych odcinków. Strukturę można zbudować w czasie $O(n\log^2n)$.

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

\end{document}