A Note on the 3-Sum Problem

سال انتشار: 1392
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 549

فایل این مقاله در 11 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_IJOCIT-1-1_002

تاریخ نمایه سازی: 16 فروردین 1395

چکیده مقاله:

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.

نویسندگان

Keivan Borna

Faculty of Mathematical Sciences and Computer Kharazmi University

Zahra Jalalian

Faculty of Engineering Kharazmi University