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

---
 barneshut.tex | 412 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 412 insertions(+)
 create mode 100644 barneshut.tex

(limited to 'barneshut.tex')

diff --git a/barneshut.tex b/barneshut.tex
new file mode 100644
index 0000000..cc2734d
--- /dev/null
+++ b/barneshut.tex
@@ -0,0 +1,412 @@
+\documentclass[twocolumn, 10pt]{article}
+
+\usepackage{geometry}
+\geometry{
+	a4paper,
+	total={6.85in, 9.92in},
+	top=16mm,
+	bottom=29mm,
+    left=18mm,
+    right=18mm,
+}
+
+% show page frame 
+\usepackage{showframe}
+
+\usepackage[utf8]{inputenc}
+\usepackage{hyperref}
+\usepackage{listings}
+\usepackage{float}
+\usepackage{tikz}
+\usepackage{forest}
+\usepackage{scrextend}
+\usepackage{caption}
+\usepackage{subfig}
+
+\pagenumbering{gobble}
+
+\title{Accelerating simulations by clustering bodies using the Barnes-Hut algorithm\vspace{-5mm}}
+\author{Paged 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[
+\vspace{-3mm}\maketitle
+]
+
+In a space with \( n \)-bodies, there are \( n-1 \) forces acting on each body.
+When simulating the forces acting on 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 \( 4 \cdot 10^{16} \). The amount of forces that need to be
+calculated can be reduced by utilizing the Barnes-Hut algorithm clustering the
+bodies resulting in much less calculations.
+
+\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 abstracted 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
+and the cluster in which the body is located can be abstracted to a single
+point.  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.35\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. (\url{http://arborjs.org/docs/barnes-hut})}
+%\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 independently, but as one object (The
+midpoint of the center of gravity is defined as a new abstract object).
+
+\begin{figure}[H]
+\centering
+\subfloat[some caption 1]{
+    \begin{tikzpicture}[level 1/.style={level distance=1.5cm}, scale=0.5, every node/.style={scale=0.66}]
+    % 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}
+}
+\subfloat[some caption 2]{
+\begin{forest}
+    for tree={circle,draw, s sep=0.2em, font=\scriptsize}
+    [
+        [A]
+        [
+            [
+                []
+                [B]
+                [C]
+                []
+            ]
+            []
+            []
+            [D]
+        ]
+        [
+            []
+            [E]
+            [F]
+            [G]
+        ]
+        [H]
+    ]
+\end{forest}
+}
+\caption{The cells defined in Figure \ref{fig:cells} displayed in the form of a quad tree. (\url{http://arborjs.org/docs/barnes-hut})}
+\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 into the tree subdividing the space if necessary.
+%        All the objects need to be places in the leaves of the tree.
+%    \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 condition. Use \( \theta \)
+%        as a threshold for controlling how many forces to take into account (\(
+%        \theta = 1 \rightarrow \) all forces, \( \theta = 0.001 \rightarrow \)
+%    almost no forces).
+%\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 \( 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 a lot of time!).
+%
+%This principle can also be used on other types of problems such as simulating
+%molecules. If you come to do something with it, write me!
+
+%\vfill
+
+\texttt{@hanemile} on most platforms.
+
+\begin{figure*}
+    %for tree={circle,draw, s sep+=0.25em}
+
+    % First
+    \begin{minipage}[t]{.24\textwidth}
+        \centering
+        % Cells
+        \begin{tikzpicture}
+            \draw (0, 0) rectangle (2, 2);
+        \end{tikzpicture}
+        ~\\
+        % Tree
+        \begin{forest}
+            for tree={circle,draw, s sep+=0.25em}
+            []
+        \end{forest}
+        % Caption
+        \captionof{figure}{Caption}
+    \end{minipage}
+    % Second
+    \begin{minipage}[t]{.24\textwidth}
+        \centering
+        % Cells
+        \begin{tikzpicture}
+            % Layer 0
+            \draw (0, 0) rectangle (2, 2);
+            
+            % Layer 1
+            \draw (0, 0) rectangle (1, 1);
+            \draw (1, 0) rectangle (2, 1);
+            \draw (0, 1) rectangle (1, 2);
+            \draw (1, 1) rectangle (2, 2);
+
+            % Nodes
+            \node at (0.25, 0.25) {A};
+        \end{tikzpicture}
+        ~\\
+        % Tree
+        \begin{forest}
+            for tree={circle,draw, s sep=3mm}
+            [
+                [][][A][]
+            ]
+        \end{forest}
+        % Caption
+        \captionof{figure}{Caption}
+    \end{minipage}
+    % Third
+    \begin{minipage}[t]{.24\textwidth}
+        \centering
+        % Cells
+        \begin{tikzpicture}
+            % Layer 0
+            \draw (0, 0) rectangle (2, 2);
+            
+            % Layer 1
+            \draw (0, 0) rectangle (1, 1);
+            \draw (1, 0) rectangle (2, 1);
+            \draw (0, 1) rectangle (1, 2);
+            \draw (1, 1) rectangle (2, 2);
+
+            % Layer 2.1
+            \draw (0, 0) rectangle (0.5, 0.5);
+            \draw (0.5, 0) rectangle (1, 0.5);
+            \draw (0, 0.5) rectangle (0.5, 1);
+            \draw (0.5, 0.5) rectangle (1, 1);
+
+            % Nodes
+            \node at (0.25, 0.25) {A};
+            \node at (0.75, 0.75) {B};
+        \end{tikzpicture}
+        ~\\
+        % Tree
+        %\begin{forest}
+        %    for tree={circle,draw, s sep=3mm}
+        %    [
+        %        []
+        %        []
+        %        [
+        %            [][][A][]
+        %        ]
+        %        []
+        %    ]
+        %\end{forest}
+        % Tree (2)
+        \begin{forest}
+            for tree={circle,draw, s sep=3mm}
+            [
+                []
+                []
+                [
+                    [][B][A][]
+                ]
+                []
+            ]
+        \end{forest}
+        % Caption
+        \captionof{figure}{Caption}
+    \end{minipage}
+    % Fourth
+    \begin{minipage}[t]{.24\textwidth}
+        \centering
+        % Cells
+        \begin{tikzpicture}
+            % Layer 0
+            \draw (0, 0) rectangle (2, 2);
+            
+            % Layer 1
+            \draw (0, 0) rectangle (1, 1);
+            \draw (1, 0) rectangle (2, 1);
+            \draw (0, 1) rectangle (1, 2);
+            \draw (1, 1) rectangle (2, 2);
+
+            % Layer 2.1
+            \draw (0, 0) rectangle (0.5, 0.5);
+            \draw (0.5, 0) rectangle (1, 0.5);
+            \draw (0, 0.5) rectangle (0.5, 1);
+            \draw (0.5, 0.5) rectangle (1, 1);
+
+            % Nodes
+            \node at (0.25, 0.25) {A};
+            \node at (0.75, 0.75) {B};
+            \node at (1.75, 1.75) {C};
+        \end{tikzpicture}
+        ~\\
+        % Tree
+        \begin{forest}
+            for tree={circle,draw, s sep=3mm}
+            [
+                []
+                [C]
+                [
+                    [][B][A][]
+                ]
+                []
+            ]
+        \end{forest}
+        % Caption
+        \captionof{figure}{Caption}
+    \end{minipage}
+\end{figure*}
+
+\end{document}
-- 
cgit 1.4.1

