From 449ba33b194f79d928663486bc24fee4d0073d4f Mon Sep 17 00:00:00 2001
From: Emile <hanemile@protonmail.com>
Date: Mon, 22 Jul 2019 15:23:42 +0200
Subject: save

---
 main.tex | 218 ---------------------------------------------------------------
 1 file changed, 218 deletions(-)
 delete mode 100644 main.tex

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
deleted file mode 100644
index 354162c..0000000
--- a/main.tex
+++ /dev/null
@@ -1,218 +0,0 @@
-\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}
-- 
cgit 1.4.1

