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

\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{amsthm}

\pagestyle{fancy}
\fancyhead[L]{Homework Exam 1 Geometric Algorithms 2024-2025}
\fancyhead[R]{Thomas van Maaren (9825827)}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}
\begin{enumerate}
\item
The algorithm works as follows. It uses a scanline starting at $y=\infty$. It also
has two balanced binary trees that keep track of the x-coordinates of the left and right sides respectively
of the squares intersecting the scanline. Every node has a size value 
which keeps track of the amount of nodes that are part of it's subtree. Whenever
the scanline comes across the top of a rectangle we simply add the left and right
x-coordinate to their respective trees. Whenever the scanline reaches a
point we calculate the
        depth as the size of the left or right tree (they have the same size) minus the amount that is left of $x$ on
the right tree and the amount that is right of $x$ on the left tree.
If our scanline reaches the end of a square we simply remove the left and right
x-coordinate from the two respective trees.
%\begin{algorithm}
%    \caption{Calculate $d_{\mathcal{R}}(p)$ for all $p\in P$}
%    \begin{algorithmic}
%        \State Initialize the binary tree $\mathcal{T}_L$ and $\mathcal{T}_R$
%        \State Initialize queue $\mathcal{Q}$ and add $P$, 
%        $(R_{x_1},R_{x_2},R_{y_2})$ for all $R\in \mathcal{R}$ and 
%        $(R_{x_1},R_{x_2},R_{y_1})$ for all $R\in \mathcal{R}$.
%        \State Sort $\mathcal{Q}$ by $y$-positions in ascending order.
%        \While{$\mathcal{Q}$ is not empty}
%            \State $q:=$ dequeue $\mathcal{Q}$
%            \If{$q\in P$}
%                \State $(x,y):=q$
%                \State $l_{\mathcal{R}}(x,y):=$nLeft($x,\mathcal{T}_R$)
%                \State $r_{\mathcal{R}}(x,y):=$nRight($x,\mathcal{T}_L$)
%                \State $d_{\mathcal{R}}(x,y):=$size($\mathcal{T}_L)-
%                l_{\mathcal{R}}(x,y)-r_{\mathcal{R}}(x,y)$
%            \EndIf
%            \If{$q$ is the top of a rectangle}
%                \State $(x_1,x_2,y_2):= q$
%                \State Add $x_1$ to $\mathcal{T}_L$
%                \State Add $x_2$ to $\mathcal{T}_R$
%            \EndIf
%            \If{$q$ is the bottem of a rectangle}
%                \State $(x_1,x_2,y_1):= q$
%                \State Remove $x_1$ from $\mathcal{T}_L$
%                \State Remove $x_2$ from $\mathcal{T}_R$
%            \EndIf
%        \EndWhile
%    \end{algorithmic}
%\end{algorithm}
%\begin{algorithm}
%    \caption{nLeft}
%    \begin{algorithmic}
%    \Procedure{nLeft}{$x,\mathcal{T}$}
%        \If{$\mathcal{T}$ is empty}
%            \State Return 0
%        \EndIf
%        \If{$x$ at root node of $\mathcal{T}$< x}
%            \State Return 1+size(left subtree of $\mathcal{T}$)+nLeft(right subtree of $\mathcal{T}$)
%            nLeft(left subtree of $\mathcal{T}$)
%        \Else
%            \State Return nLeft(left subtree of $\mathcal{T}$)
%        \EndIf
%    \EndProcedure        
%    \end{algorithmic}
%\end{algorithm}

For every $R\in\mathcal{R}$ we will denote the left and right x-coordinate wit
$R_{x_1}$ and $R_{x_2}$ respectively and $R_{y_1}$ and $R_{y_2}$ denote the 
bottem and top y-coordinate respectively.

\begin{lemma}
    The algorithm computes $d_{\mathcal{R}}(p)$ for all $p\in P$ correctly.
\end{lemma}
\begin{proof}
    Remember that the priority of an event is given by its y-coordinate, and
    that because no points or vertices are co-linear it can never happen that
    that vertex of a rectangle shares a y-coordinate with a point. We shall
    prove the lemma by induction over the events in the queue.

    Let $q$ be the newest event in the queue. Assume as a induction hypothesis
    that all points with a higher y-coordinate have been computed correctly and
    that the left and right tree consist exactly of the squares intersecting
    the previous sweepline. The induction basis is true, because when
    $y=\infty$ no squares intersect the sweep line and no points have been
    passed.
    
    Assume that the next queue element is a point $p\in P$. Because the queue
    is sorted there has not been a bottem or top of a square since last
    iteration, hence the left tree and right tree represent the set of left
    x-coordinates and right x-coordinate intersecting sweep line going through
    $p$. We therefore know that the squares containing $p$ form a subset of
    what is in the trees. We know that $p$ is in rectangle $R$ if and only if
    $R_{x_1}\leq p_x \leq R_{x_2}$ or equivalently not $R_{x_1}> p_x$ or $p_x>
    R_{x_2}$. Because $R_{x_1}<R_{x_2}$ we see that both sets of squares are
    disjoint. Therefore the amount of squares that contain $p$ are the amount
    of squares currently in the tree minus the amount squares where $R_{x_1}>
    p_x$ or $p_x>R_{x_2}$ hold. These are exactly the squares that are
    right to $p_x$ in left tree or are left to $p_x$ in the right tree, hence
    we have correctly calculated $d_{\mathcal{R}}(p)$ and the induction
    hypothesis remains true.

    Assume that the queue event is the top of a rectangle. Because no vertices
    of two different square can be the same, we see that when this square is
    added to the trees that the trees contain exactly the squares that are on
    the current sweep line
   
    If the queue event is the bottem of a rectangle then this rectangle is no
    longer intersected by the sweep line, hence
    by removing it from the trees ensures that the trees contain exactly the 
    the squares that are on the current sweep line.

    We conclude that when the sweep line has passed all of the events, that the
    property in the induction hypothesis still holds, hence we have proven that
    the algorithm computes $d_{\mathcal{R}}(p)$ for all $p\in P$ correctly.
\end{proof}

\begin{lemma}
    The algorithm takes $o((n+m)log(n+m))$ time. 
\end{lemma}
\begin{proof}
    In the beginning all points, tops of squares and bottem of squares are
    sorted. This takes $o((n+m)log(n+m))$-time. After that it has to pass all
    $o(n+m)$ events. For each event it has to either add an element to the
    binary trees, do a binary search or remove an element from the binary
    trees. All These operations take $o(\log m)$-time, hence handling the queue
    takes $o(n+m)o(\log m)$-time. Thus our algorithm takes
    $o((n+m)log(n+m))$-time.
\end{proof}

Because of lemma 1 and 2 we can conclude the following:

\begin{theorem}
    Calculating the depth of $n$ points given $m$ rectangles takes
    $o((n+m)\log(n+m))$-time.
\end{theorem}

\item

Because all triangles have one edge that is aligned to one of the axes, we have
four types of triangles to work with. In the answer I will only look at the
cases that an edge is aligned with x-axis and that this edge is on the top of
the triangle. This is possible because we can handle the types of triangles
seperately. For every type we rotate and/or flip the the plane such that we get
the types of triangles as stated earlier. This process takes linear time. The
process for the specified type of
triangles will be very similar with exercise 1. Just as in exercise we we will
have an event que consisting of the points, top triangles and bottem of
triangles. Whenever the scanline reaches the top of a triangle it's leftmost
point and rightmost point are added to left and right tree respectively. The
difference is how different points are compared. We cannot simply compare
the x-coordinates, because the edges do not run vertically anymore. Now we also
have to take the y-coordinate in consideration. In the left tree we will say
that point $(x_1,y_1)$ is left of $(x_2,y_2)$ if and only if 
$x_1\cos 30^\circ +y_2\sin 30^\circ < x_2\cos 30^\circ +y_2\sin 30^\circ$. In
right tree we will say that $(x_1,y_1)$ is left of $(x_2,y_2)$ if and only if
$x_1\cos 30^\circ -y_2\sin 30^\circ < x_2\cos 30^\circ -y_2\sin 30^\circ$

\item

Our method for squares and rectangles will not work for arbitrary triangles. 
This is because whenever we add a triangle to our binary trees, the order of edges
could change in any way in the future. Hence we have to look at possible intersections,
hence the time-complexity when using our method cannot simply depend on the
amount of triangles and points.
\end{enumerate}
\end{document}
        %    \If{$\mathcal{T}$ is empty}
        %        \State Return 0
