\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}