basic structure

4 files changed, 220 insertions, 0 deletions

diff --git a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf
new file mode 100644
index 0000000..3d55efd
--- /dev/null
+++ b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf
Binary files differdiff --git a/current-build b/current-build
new file mode 120000
index 0000000..2fd5fed
--- /dev/null
+++ b/current-build
@@ -0,0 +1 @@
+build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672
\ No newline at end of file
diff --git a/last-successful b/last-successful
new file mode 120000
index 0000000..2fd5fed
--- /dev/null
+++ b/last-successful
@@ -0,0 +1 @@
+build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672
\ No newline at end of file
diff --git a/main.tex b/main.tex
new file mode 100644
index 0000000..354162c
--- /dev/null
+++ b/main.tex
@@ -0,0 +1,218 @@
+\documentclass[twocolumn, 10pt]{article}
+
+\usepackage{geometry}
+\geometry{
+	a4paper,
+	total={6.85in, 9.92in},
+	left=0.71in,
+	top=0.63in,
+}
+\usepackage[utf8]{inputenc}
+\usepackage{hyperref}
+\usepackage{listings}
+
+% custom imports
+\usepackage{float}
+\usepackage{tikz}
+\usepackage{forest}
+
+\pagenumbering{gobble}
+
+\title{Clustering bodies using the Barnes-Hut algorithm accelerating simulations}
+\author{Page Out!}
+
+\makeatletter
+\newcommand{\fsize}{\f@size pt }
+\newcommand{\textFontName}{\f@family}
+\renewcommand{\maketitle}{
+\begin{flushleft}
+{\noindent\Huge\bf\@title}\break
+\end{flushleft}
+}
+\makeatother
+
+
+\begin{document}
+\twocolumn[
+\maketitle
+]
+
+In a space with \( n \)-bodies, there are \( n-1 \) forces acting on each body.
+When simulating all the bodies, \( n \cdot (n-1) \) forces need to be
+calculated for estimating the new position of the individual bodies. With a big
+enough amount of bodies, this gets problematic. Let's take a real galaxy with
+\( 2 \cdot 10^{8} \) Stars. The total amount of forces that need to be
+calculated are about \( 4 \cdot 10^{16} \).
+
+This can be reduced by utilizing the Barnes-Hut algorithm clustering the bodies.
+
+\begin{figure}[H]
+\centering
+    \begin{tikzpicture}
+        \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm]
+        \node at (0, 0) {};
+        \node at (9, 0) {};
+
+        % Random seed for RNG
+        \pgfmathsetseed{7};
+
+        \foreach \x in {1,...,40}
+        {
+          % Find random numbers
+          \pgfmathrandominteger{\a}{10}{390}
+          \pgfmathrandominteger{\b}{10}{390}
+
+          % Scale numbers nicely
+          \pgfmathparse{0.005*\a}\let\a\pgfmathresult;
+          \pgfmathparse{0.005*\b}\let\b\pgfmathresult;
+
+          % draw the circle
+          \fill (\a, \b) circle (0.03);
+        };
+
+        % draw a box around the star cluster
+        \draw[] (0,0) rectangle (2, 2);
+        \node[] at (1, 1) (A1) {};
+        \draw[arrows=<->] (0,-0.2) -- node[midway, align=center, below] {\(d\)} (2,-0.2);
+
+        % draw a star in the far right of the image
+        \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 1) (A2) {};
+
+        % draw a line in between the box and the far right of the image
+        \draw[dashed, arrows=<->] (A1) -- node[midway, align=center, above] {\(r\)} (A2);
+    \end{tikzpicture}
+\end{figure}
+~\\[-1.5cm]
+\begin{figure}[H]
+    \centering
+    \begin{tikzpicture}
+        \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm]
+        \node at (0, 0) {};
+        \node at (9, 0) {};
+
+        % draw a big star in the far left of the image
+        \node[circlestyle, minimum size=2pt, label=above:\(q_1\)] at (1, 0) (B1) {};
+
+        % draw the right star
+        \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 0) (B2) {};
+
+        % draw a line in between the far left star and the right star
+        \draw[dashed, arrows=<->] (B1) -- node[midway, align=center, above] {\(r\)} (B2);
+    \end{tikzpicture}
+    \label{subfig:grouped}
+    \caption{A cluster of stars that is far enough away from a single star can
+    be summed up as a single point in space.}
+\end{figure}
+
+\begin{equation} \label{eqn:barnes-hut}
+    \theta = \frac{d}{r}
+\end{equation}
+
+The above equation describes how to cluster the stars. If a body is far away
+(\( >> r\)) from a small cluster (\( << d \) ), \( \theta \) get's very small.
+By defining a theta as a threshold, we can define what clusters we take into
+effect when calculating the forces acting on a single star.
+
+In order to do so, the space in which the objects are defined needs to be
+subdivided into cells.  Such a subdivision can be seen in Figure
+\ref{fig:cells}.
+
+\begin{figure}[H]
+\hspace{1.5cm}
+\begin{minipage}{0.45\linewidth}
+\begin{tikzpicture}[level 1/.style={level distance=1.5cm}]
+    % First Layer
+    \draw [line width=0.5mm] (0, 0) rectangle (6, 6);
+
+    % Second Layer 
+    \draw [line width=0.25mm] (0, 0) rectangle (3, 3);
+    \draw [line width=0.25mm] (3, 0) rectangle (6, 3);
+    \draw [line width=0.25mm] (0, 3) rectangle (3, 6);
+    \draw [line width=0.25mm] (3, 3) rectangle (6, 6);
+
+    % Third Layer (South West)
+    \draw [line width=0.125mm] (0, 0) rectangle (1.5, 1.5);
+    \draw [line width=0.125mm] (1.5, 1.5) rectangle (3, 3);
+
+    % Third Layer (North East)
+    \draw [line width=0.125mm] (3, 3) rectangle (4.5, 4.5);
+    \draw [line width=0.125mm] (4.5, 4.5) rectangle (6, 6);
+
+    % Forth Layer (North West)
+    \draw [line width=0.125mm] (3, 4.5) rectangle (3.75, 5.25);
+    \draw [line width=0.125mm] (3.75, 5.25) rectangle (4.5, 6);
+
+    % Draw the nodes
+    \node at (1, 4.5) {$A$};
+    \node at (4, 5.5) {$B$};
+    \node at (3.5, 5) {$C$};
+    \node at (5, 4) {$D$};
+    \node at (2.75, 2.75) {$E$};
+    \node at (0.75, 0.75) {$F$};
+    \node at (2, 0.75) {$G$};
+    \node at (3.5, 0.75) {$H$};
+\end{tikzpicture}
+\end{minipage}
+\caption{Subdivision of a 2D Space containing some bodies.}
+\label{fig:cells}
+\end{figure}
+
+When calculating the forces on let's say the object \( F \), not all other
+objects need to be taken into effect, only the ones that apply to the
+Barnes-Hut Principle.  For the object \( F \), this means that the Objects \( C
+\) and \( D \) are not calculated independantly, but as one object (The
+midpoint of center of gravity is defined as a new object).
+
+\begin{figure}[H]
+\centering
+\begin{forest}
+    for tree={circle,draw, s sep+=0.25em}
+    [
+        [A]
+        [
+            [
+                []
+                [B]
+                [C]
+                []
+            ]
+            []
+            []
+            [D]
+        ]
+        [
+            []
+            [E]
+            [F]
+            [G]
+        ]
+        [H]
+    ]
+\end{forest}
+\caption{The cells defined in Figure \ref{fig:cells} dispayed in the form of a quadtree.}
+\label{fig:tree}
+\end{figure}
+
+In order to simulate the change of position for all objects in the given space,
+a tree can be used.  The tree in Figure \ref{fig:tree} describes the cells from
+Figure \ref{fig:cells} in a form that can be easily programmed. The complete
+process of simulating works in the following way:
+
+\begin{enumerate}
+    \item Define an empty space.
+    \item Insert the objects subdividing the space if necessary.
+    \item Calculate the center of mass and the total mass for all inner nodes in the tree.
+    \item For calculating the force acting on a star, walk through the tree
+        from the root in direction of the leaves, using the Barnes-Hut
+        Algorithm (\ref{eqn:barnes-hut}) as an end codition.
+\end{enumerate}
+
+In the end, when simulating a lot of bodies, the runtime is optimized from \(
+O(n^2) \) to \( O(n \cdot \log(n)) \). This means that if you've got \( 2 \cdot
+10^8 \) bodies and can calculate the forces acting on \( 1 \cdot 10^6 \) bodies
+bodies per second, the total runtime is reduced from about 1200 Years to 45
+minutes (this is just the calculation of the forces, inserting the bodies into
+the tree takes alot of time!).
+
+
+\end{document}