\documentclass[unbewertet]{agisuebung}

\date{04.~Februar 2025}
%\newcommand{\deadlineDate}{Mittwoch, 06.~November 2024, 12:15~Uhr}
\newcommand{\exerciseNum}{4}
\usepackage{multicol}

% # # # # # # # # # # # # # # # # # # # # # # # # # #
\begin{document} %  # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #


\begin{aufgabe}[Algorithmus von de Berg et al.]
Betrachten Sie für diese Aufgabe den Algorithmus zur Flächenvereinfachung wie er in der Vorlesung vorgestellt wurde.
\begin{teilaufgabe}
\item In der Vorlesung wurde behauptet, dass die Methode Punktzuweisung die Laufzeit $\Oh((n + m) \log n)$ besitzt. Die Methode benötigt so wie aufgeschrieben allerdings $\Oh((n+m)\log (n+m))$ Zeit. Warum? Wie können wir die Methode anpassen, so dass sie tatsächlich in $\Oh((n+m)\log n)$ Zeit läuft?
\item Überlegen Sie sich basierend auf geometrischen Beobachtungen ein Beschleunigungsverfahren, mit dessen Hilfe die Punktmenge $P$ eingeschränkt werden kann.
\item Überlegen Sie sich ein Beschleunigungsverfahren, mit dessen Hilfe die Konsistenzberechnung von shortcuts beschleunigt werden kann. 
\end{teilaufgabe}
Hinweis zu 2. und 3.: Es ist nicht nötig, die Laufzeit für den schlimmsten anzunehmenden Fall zu
verbessern, sondern es reicht aus, sich Beschleunigungstechniken zu überlegen, die in der Praxis
gut funktionieren könnten.
\end{aufgabe}

% ### aufgabe
\begin{aufgabe}[Rechtecksduale skalieren]
Gegeben sei ein Rechtecksdual $\mathcal R$ bestehend aus den Rechtecken
$R_1, \dots, R_n$ sowie dessen hierarchische Rechteckszerlegung
$\mathcal H$. Nehmen Sie an, dass die Rechtecke zerschneidbar sind, also
jeder Knoten in $\mathcal H$ maximal zwei Nachfolger
hat.
\begin{teilaufgabe}
 \item Beschreiben Sie ein Verfahren, das basierend auf $\mathcal R$ und
$\mathcal H$ die Größen von $R_1, \dots, R_n$ so anpasst, dass die
entsprechenden Flächen mit vorgegebenen Werten $A_1, \dots, A_n$
übereinstimmen.
\item Erhält Ihr Verfahren die von $\mathcal R$ vorgegebenen Nachbarschaften?
\end{teilaufgabe}
\end{aufgabe}

\begin{aufgabe}[L-zerlegbare Rechtsecksduale]
Betrachten Sie das Rechtecksdual aus Abbildung~\ref{fig:R5} bestehend
aus den Rechtecke $R_1, \dots, R_5$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
 \draw (0,0)--(3,0)--(3,3)--(0,3)--(0,0);
 \draw (0,2)--(2,2) (1,1)--(3,1);
 \draw (1,0)--(1,2) (2,1)--(2,3);
\end{tikzpicture}
\end{center}
\caption{Ein Rechtecksdual aus fünf Flächen.}\label{fig:R5}
\end{figure}

\begin{teilaufgabe}
 \item Zeigen Sie, wie aus diesem Dual für gegebene Flächenwerte $A_1, \dots, A_5$ ein
Rechteckskartogramm erstellt werden kann, sodass jedes Rechteck $R_i$ die Fläche
$A_i$ besitzt und die Nachbarschaften erhalten bleiben.

\item Kann man das von Ihnen angegebene Vorgehen auf alle L-zerlegbaren
Reckecksduale anwenden, wenn die Nachbarschaften dabei zerstört werden dürfen? 
Wenn ja, wie? Wenn nein, warum nicht?

\item Kann man das von Ihnen angegebene Vorgehen auf alle Rechtecksduale
anwenden, wenn die Nachbarschaften dabei zerstört werden dürfen? Wenn ja, wie? Wenn nein, warum nicht?
\end{teilaufgabe}
\end{aufgabe}


% # # # # # # # # # # # # # # # # # # # # # # # # # #
\end{document} %  # # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #