A Note on the 3-Sum Problem

The 3-Sum problem for a given set S of integers is subject to find all three-tuples (a, b, c) for which a + b + c = 0. In computational geometry many other problems like motion planning relate to this problem. The complexity of existing algorithms for solving 3-Sum are O(n2) or a quotient of it. The aim of this paper is to provide a linear hash function and present a fast algorithm that finds all suitable three-tuples in one iteration of S. We also improve the performance of our algorithm by using index tables and dividing S into two negative and non-negative parts.