\documentclass{article}
\usepackage{fancyhdr}
\usepackage[margin=2cm]{geometry}

\pagestyle{fancy}
\fancyhead[L]{Homework Exam 1 2024-2025}
\fancyhead[R]{Thomas van Maaren (9825827)}

\begin{document}

\begin{enumerate}
    \item We will use a scanline together with a balanced binary tree. Just as in the
          the algorithm in the lecture there will be some scanline events.
          The events are in our case:
          \begin{itemize}
            \item The scanline reaches the start of a rectangle
            \item The scanline reaches a point
            \item The scanline reaches the the end of a rectangle
          \end{itemize}
          Our binary tree consists of the x-positions of rectangles. When the
          scanline reaches the start of a rectangle the x position of the left
          and right edges over the rectangle are added to the binary tree. We also
          give these new nodes two empty leaves. We want to efficiently keep
          track of the depth of a certain area. 

          If a node is on the path from the root to the x-coordinate of the
          left x-position, but not on the path from the root to the
          x-coordinate of the right x-position and that the left child goes to
          the x-coordinate of the left edge, we know that the right child is
          definitely inside the rectangle. Therefore we can increase it's value
          by one.

          Conversely, if a node is on the path from the root to the x-coordinate of the
          right x-position, but not on the path from the root to the
          x-coordinate of the left edge and that the right child goes to
          the x-coordinate of the right edge, we know that the left child is
          definitely inside the rectangle. Therefore we can increase it's value
          by one.

          Whenever the scanline reaches a point, we look at it's x position
          and look at it's path through the binary tree. We then sum up the value
          of all the nodes that is passes. This is then the depth of that point.

          Whenever the scanline reaches the end of a rectangle we simply remove
          do the reverse of what we did at the start of the rectangle. Meaning
          that we lower the values of the apropriate nodes from the binary tree.

          We will now provide the algorithm and then we will provide the algorithm

          \begin{verbatim}
          Create a queue Q of all the different points, rectangle starts and rectangle ends.
          Sort the queue by y-position
          Initialize tree as a leaf with value 0
          for event in queue:
            HandleEvent(event)
          \end{verbatim}

          \begin{verbatim}
          HandleEvent(event)
            if event is a point:
                Let x_1,...,x_k be the values corresponding to the nodes of the path of point.x on the binary tree.
                d_R(p) = sum_{i=1}^n x_k
            if event is a start of rectangle:
                Add the x position of the left and right side of the rectangle
                to the tree.
                x1:= x position of the left edge of event
                x2:= x position of the right edge of event
                node:= root of tree
                while node is not a leaf:
                    if node.x < x1:
                        node = right child of node
                    else:
                        
                        node = left child of node

            if event is an end of rectangle:
          \end{verbatim}

\end{enumerate}

\end{document}
        %output: dept for every point
        %\textbf{Algorithm} FindDepth
        %\begin{enumerate}
        %    \item Initialize an empty event que $\mathcal{Q}$. Next, insert the
        %          points. For every square we add an item that holds the top
        %          y-position and left-and right x position. We also hold a
        %          seperate item for every square that holds the bottem y-position
        %    \item Sort $\mathcal{Q}$ by y-position.
        %    \item Initialize an empty status structure $\mathcal{T}$.
        %    \item \textbf{while} $\mathcal{Q}$ is not empty
        %    \item \ \ \textbf{Do} Determine the next event point $p$ in $\mathcal{Q}$
        %          and delet it.
        %    \item \ \ \ \ HandleEventPoint(p)
        %\end{enumerate}

        %HandleEventPoint(p)
        %\begin{enumerate}
        %    \item \textbf{If} $p$ is a point 
        %    \item \ \ \textbf{Then}
        %    \item \ \ \ \ node := root of $\mathcal{T}$
        %    \item \ \ \ \ $d_{\mathcal{R}}(p) := 0$
        %    \item \ \ \ \ \textbf{While} node is not a leaf
        %    \item \ \ \ \ \ \ \textbf{Do}
        %    \item \ \ \ \ \ \ \ \ \textbf{If} node¸x $< p_x$
        %    \item \ \ \ \ \ \ \ \ \ \ \textbf{Then} node := right child of node
        %    \item \ \ \ \ \ \ \ \ \textbf{Else}
        %    \item \ \ \ \ \ \ \ \ \ \ node := left child of node
        %    \item \ \ \ \ \ \ \ \ $d_{\mathcal{R}(p)= $d_{\mathcal{R}(p)$+value of node
        %    \item \textbf{If} $p$ is the top of a square
        %    \item \ \ \textbf{Then}
        %    \item \ \ \ \ Add leftTop and rightTop to $\mathcal{T}$.
        %    \item \ \ \ \ node := root of $\mathcal{T}$
        %    \item \ \ \ \ $d_{\mathcal{R}}(p) := 0$
        %    \item \ \ \ \ \textbf{While} node is not a leaf
        %    \item \ \ \ \ \ \ \textbf{Do}
        %    \item \ \ \ \ \ \ \ \ \textbf{If} node¸x $< p_{x_1}$
        %    \item \ \ \ \ \ \ \ \ \ \ \textbf{Then} node := right child of node
        %    \item \ \ \ \ \ \ \ \ \textbf{Else}
        %    \item \ \ \ \ \ \ \ \ \ \ node := left child of node
        %    \item \ \ \ \ \textbf{While} node is not root of $\mathcal{T}$
        %    \item \ \ \ \ \ \ \textbf{Do}
        %    \item \ \ \ \ \ \ \ 
        %    \item \ \ \ \ \ \ \ \ 
        %\end{enumerate}