A Note on the 3-Sum Problem
Publish Year: 1392
نوع سند: مقاله ژورنالی
زبان: English
View: 613
This Paper With 11 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_IJOCIT-1-1_002
تاریخ نمایه سازی: 16 فروردین 1395
Abstract:
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.
Keywords:
Authors
Keivan Borna
Faculty of Mathematical Sciences and Computer Kharazmi University
Zahra Jalalian
Faculty of Engineering Kharazmi University