-
Notifications
You must be signed in to change notification settings - Fork 0
/
introduction.tex
71 lines (59 loc) · 10.7 KB
/
introduction.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
% ================================================================================
% --------------------------------------------------------------------------------
\section{Introduction}
\label{s:introduction}
% --------------------------------------------------------------------------------
We consider the \texttt{3SUM} problem and its limited to only integers version \texttt{Int3SUM}, a variant of this, one of the most basic problems in algorithm design, which are defined as follows:
\begin{definition}[\texttt{3SUM}]
Given a set $S \subset \mathbb{R}$, $|S| := n$, determine if there exists $n_{1}, n_{2}, n_{3} \in S$ such that $n_{1} + n_{2} + n_{3} = 0$.
\label{def:3sum}
\end{definition}
\begin{definition}[\texttt{Int3SUM}]
Given a set $S \subseteq \{-U, \dots, U\} \subset \mathbb{Z}$, $|S| := n$, determine if there exists $z_{1}, z_{2}, z_{3} \in S$ such that $z_{1} + z_{2} + z_{3} = 0$.
\label{def:int3sum}
\end{definition}
Since numerous problems can be reduced from \texttt{3SUM} \cite{gajentaan1995class} \cite{barequet2001polygon}, it has raised wide interest. Such problems which are at least as hard as \texttt{3SUM} are called \textit{3SUM-Hardness}. Some of them are ...
\begin{itemize}
\item Given a $n$-point set in the plane, determine if it contains three collinear points. It was shown by Gajentaan and Overmars \cite{gajentaan1995class} that it can be solved in $\mathcal{O}\left(n^{2}\right)$ time.
\item Given a set of $n$ triangles in the plane, determine if their union contains a hole or not, respectively compute the area of their union which can be also solved in $\mathcal{O}\left(n^{2}\right)$ time \cite{gajentaan1995class}.
\item Given two $n$-poin sets $X, Y \subset \mathbb{R}$, each of size $n$, determine if all elements in $X + Y = \{x + y \, | \, x \in X, y \in Y\}$ are distinct. It can be solved in $\mathcal{O}\left(n^{2}\log\left(n\right)\right)$ time \cite{barequet2001polygon}. This problem, including its stronger version with sorting $X + Y$, is used for the conditional lower bounds of problems by Barequet and Har-Peled in \cite{barequet2001polygon} and are classified as \textit{Sorting $X + Y$-Hard}. It's an open question if it can be solved in $o\left(n^{2}\log\left(n\right)\right)$ \cite{TheOpenP60:online} \cite{TheOpenP60:onlineP11} \cite{TheOpenP60:onlineP41}.
\item Given two $n$-edge convex polygons, determine if one can be placed inside the other by translation and rotation which can also be solved in $\mathcal{O}\left(n^{2}\log\left(n\right)\right)$ time \cite{barequet2001polygon}.
\item ... .
\label{it:3sumhardnessproblems}
\end{itemize}
So, it turns out that examinations of \texttt{3SUM} are a starting point for wide studies of problem statements in computational geometry.
% --------------------------------------------------------------------------------
\subsection{Related Work}
\label{ss:relatedwork}
% --------------------------------------------------------------------------------
The lower bound of computational complexity of \texttt{3SUM} is a long standing unsolved question. Over the years, work has been done and several results were achieved.
\begin{itemize}
\item A trivial hash table algorithm can solve \texttt{3SUM} in $\mathcal{O}\left(n^{2}\right)$ time.\\
All elements $s \in S$ are hashed into a table $T_{h}$ by $h\left(s\right)$. Then we go for all $\left(h\left(s_{i}\right) + h\left(s_{j}\right)\right)$ through the hash table and check for $-\left(h\left(s_{i}\right) + h\left(s_{j}\right)\right)$.
\item Erickson \cite{erickson1995lower} credited Seidel \cite{edelsbrunner1986constructing} that \texttt{Int3SUM} can be solved with fast Fourier transform in $\mathcal{O}\left(n + U\log\left(U\right)\right)$ time, for a universe size $U$ (an integer range $[-U, \dots, U]$) \cite{harper1975sorting}.
\item Baran, Demaine and Pǎtra{\c{s}}cu \cite{baran2005subquadratic} showed that \texttt{Int3SUM} can be solve in $\mathcal{O}\left(n^{2}/\left(\log\left(n\right)/\log \log\left(n\right)\right)^{2}\right)$ time with high probability on the word RAM with $U = 2^{\omega}$ and $\omega > \log\left(n\right)$ is the machine word size. It uses a mixture of randomized universe reduction by hashing, word packing and table lookups.
\item Erickson \cite{erickson1995lower} and Ailon and Chazelle \cite{ailon2005lower} proved that any $3$-linear decision tree for \texttt{3SUM} has depth $\Omega\left(n^{2}\right)$ and matching $\Omega\left(n^{\lceil k/2 \rceil}\right)$ lower bounds in some particular models.
\item Grønlund and Pettie \cite{grnlund2014threesomes} showed that \texttt{3SUM} can be solved in subquadratic time by a deterministic algorithm which runs in $\mathcal{O}\left(n^{2}\left(\log\left(n\right) / \log \log\left(n\right)\right)^{2/3}\right)$ time and a randomized algorithm which runs in $\mathcal{O}\left(n^{2}\left(\log \log\left(n\right)\right)^{2} / \log \left(n\right)\right)$ expected time with high probability. They also showed that it exists a $4$-linear decision tree with deph $\mathcal{O}\left(n^{3/2} \sqrt{\log\left(n\right)}\right)$.
\item Freund \cite{freund2017improved} developed a \texttt{3SUM} algorithm by eliminating one of Grønlund and Pettie's conceptual building blocks and lead to a bound for running time of $\mathcal{O}\left(n^{2} \log \log\left(n\right)/\log\left(n\right)\right)$.
\item Gold and Sharir \cite{gold_et_al:LIPIcs:2017:7836} showed that the randomized $4$-linear decision tree complexity of \texttt{3SUM} is $\mathcal{O}\left(n^{3/2}\right)$.
\item Chan \cite{chan2019more} gave an algorithm that solved \texttt{3SUM} in $\mathcal{O}\left(\left(n^{2}/\log\left(n\right)\right)\left(\log \log\left(n\right)\right)^{\mathcal{O}\left(1\right)}\right)$ time and obtained subquadratic results on some \texttt{3SUM}-hard problems.
\item Kane, Lovett, and Moran \cite{kane2017nearoptimal} constructed a linear decision tree that solves the \texttt{3SUM} problem with $\mathcal{O}\left(n \log^{2}\left(n\right)\right)$ queries which compare the sums of two $3$-subsets.
\item Kopelowitz, Pettie and Porat \cite{kopelowitz2014higher} conjectured that \texttt{3SUM} is unsolvable in $\mathcal{O}\left(n^{2 - \omega\left(1\right)}\right)$ expected time.
\label{it:realtedwork}
\end{itemize}
In this work, we want to present a new kind of algorithm design, different compared to the mentioned works. We can see, that apart from Seidel's \cite{edelsbrunner1986constructing} Fast Fourier transformation and Baran, Demaine and Pǎtra{\c{s}}cu's \cite{baran2005subquadratic} work which used randomized universe reducation, word packing and table lookups, for \texttt{Int3SUM}, these works are all mainly based on decision trees and queries depending on the numbers of $S$ in decimal representation. We not want to do this kind of approach again. Instead, we will use a new angle of view based on the binary representation of the numbers of $S$ and the characteristics of binary addition.
% --------------------------------------------------------------------------------
\subsection{Our Results}
\label{ss:ourresults}
% --------------------------------------------------------------------------------
In this work, we start with the basic idea of using an algorithm for the \texttt{3SUM} problem on the binary representation level of numbers in a computer system, which means using the nature of binary number addition on a bit level instead of comparing the numbers in their total representation.
The first problem which raises are the set of irrational numbers, since their can't be represented exactly by a finite number of bits. We show that we can solve this problem by a mapping of irrational numbers to a zero sum question of their rational factors, instead. To reach this, we introduce a concatenation representation of real numbers $n_{i}$, based on a finite set $\mathbb{I}_{a}$ of so called \textit{Atomic irrational numbers}.
Since, we see that we are able to solve the real number problem by solving the problem for rational numbers, we examine existing representations like \textit{Floating-point arithmetic} and \textit{Fixed-point arithemetic}. Since, both of this representations would raise the complexity of our algorithm idea exponentially, we introduce so called \textit{Fixed-point integer arithmetic}. This way of representation of a rational number consists simple by represent the pre radix point part of our number by one integer and the post radix point part of our number by a second additional integer. Although, obviously standard binary addition for the whole number in this way is no longer possible, this way of representation gives us the possiblity to save space and time.
We examine the properties of the zero sum addition of three integer numbers and receive a set of rules $\mathcal{C}$ which tells us how much $0$s and how much $1$s we need, by a given carrier $c{[q]}$ at bit position $q$, to receive a zero sum bit at position $q$. Since, the successors of such rules turn out to be unique, we can take this rules to determine valid soulutions.
For this we define two kinds of binary trees: a list entries tree $T$ which contains the given list numbers $n_{i}$ and string trees $T^{string}$ which constains the given rules and the final solutions after $b + 1$ bit depth steps. By connecting this two tree kinds we receive for the \texttt{3SUM} problem of a list $L$ of $n$ elements, a time complexity of $\mathcal{O}\left(nb + U^{1.58}\right)$ and space complexity of $\mathcal{O}_{Space}\left(nb + U^{1.58}\right)$ for an universe of $U := 2^{b}$ distinguishable rational numbers and $\mathcal{O}\left(nb|\mathbb{I}_{a}| + U^{1.58}_{\mathbb{I}_{a}}\right)$ on an universe of $U_{\mathbb{I}_{a}} := 2^{b |\mathbb{I}_{a}|}$ distinguishable real numbers $n_{i}$ with a space complexity $\mathcal{O}_{Space}\left(nb|\mathbb{I}_{a}| + U^{1.58}_{\mathbb{I}_{a}}\right)$, too.
% --------------------------------------------------------------------------------
\subsection{Organization}
\label{ss:organization}
% --------------------------------------------------------------------------------
Our notes are organized as follows. In section \ref{s:preliminaries}, we start with giving some necessary basic definitions and notations. In section \ref{s:zerosumbitaddition}, we discuss basic properties of real numbers, the necessities of a particular way of irrational number representation and deriving from this, we introduce \textit{Atomic irrational numbers}. Then, we determine the characteristics of zero sum addition on a binary representation level of numbers, to derive a set of rules, which we use for our \texttt{3SUM} algorithm in section \ref{s:thegeneralalgorithm}. Finally, in section \ref{s:algorithmcomplexities} we discuss the belonging complexities of our presented algorithm.
% ================================================================================