Keivan Borna - Faculty of Mathematical Sciences and Computer Kharazmi University
Zahra Jalalian - Faculty of Engineering Kharazmi University

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 algorithmthat 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.

3-Sum Problem, Computational Complexity, Linear Hash Function, Motion Planning